Содержание к диссертации
Введение
Глава 1. Модели, методы и алгоритмы обработки информации в стохастических каналах связи 11
1.1. Постановка задачи 11
1.2. Модель непрерывного канала связи со случайными характеристиками .. 12
1.2.1. Каноническая схема цифровой системы связи 12
1.2.2. Модели непрерывных каналов связи 15
1.2.3. Оптимальный прием в непрерывном канале 18
1.2.4. Субоптимальные отображения каналов связи 20
1.3. Модели полунепрерывных каналов связи 23
1.3.1. Модель канала связи со стиранием элементов 23
1.3.2. Функции правдоподобия для двоичного симметричного канала связи 27
1.3.3. Последовательный детектор максимального правдоподобия 29
1.3.4. Способ получения оценок надежности символов в стирающем канале связи 31
1.4. Анализ методов декодирования групповых кодов 34
1.4.1 Алгебраические методы декодирования 34
1.4.2 Неалгебраические методы декодирования 41
1.4.3 Мягкое декодирование 44
1.5. Выводы 46
Глава 2. Модели негауссовских каналов связи со стираниями 47
2.1. Постановка задачи 47
2.2. Модель марковского двоичного канала со стираниями 48
2.3. Стирающий канал при воздействии импульсных помех 57
2.4. Параметры модели дискретного канала со стираниями 64
2.5. Выводы 69
Глава 3. Разработка алгоритмов неалгебраического декодирования систематических кодов 70
3.1. Постановка задачи 70
3.2. Кластерный подход к декодированию полиномиальных кодов 71
3.3. Декодирование на основе лучших показателей приема сигнала 88
3.4. Синтез алгоритмов функционирования декодера 96
3.5. Выводы 101
Глава 4. Программная реализация разработанных алгоритмов и оценка их эффективности 102
4.1 Постановка задачи 102
4.2. Модель Гауссовского канала связи со стиранием элементов 103
4.2.1. Принцип моделирования непрерывного канала связи с АБГШ 103
4.2.2. Моделирования системы связи с избыточным кодированием 104
4.3 Оценка эффективности разработанных алгоритмов методом
имитационного моделирования 107
4.4. Выводы 111
Заключение 112
Библиографический список
- Модель непрерывного канала связи со случайными характеристиками
- Функции правдоподобия для двоичного симметричного канала связи
- Модель марковского двоичного канала со стираниями
- Кластерный подход к декодированию полиномиальных кодов
Введение к работе
Актуальность исследования
Развитие современных телекоммуникационных систем основывается на быстрых технологических изменениях, которые позволяют строить высокоскоростные сети связи с широким спектром услуг. Требуемое качество обслуживания в них определяется рядом технических решений, в котором видную роль играет система управления сетевыми ресурсами, определяющая гибкость и эффективность работы капиталоемкого оборудования сети. В отличие от информационных каналов, использующих непрерывные коды, системы управления используют блоковые коды, которые по своей природе в большей степени отвечают требованиям по передаче информации управления в форме отдельных ячеек.
Требования к каналам управления по достоверности и скорости обработки данных оказываются выше аналогичных требований для информационных потоков. Это ограничивает применение методов перемежения символов и накладывает на корректирующий код дополнительную нагрузку. Известно, что исправление трех и более ошибок групповыми кодами в метрике Хемминга, приводит к значительному росту сложности декодера.
Попытки решить эту задачу привели к неалгебраическим методам обработки комбинаций избыточных кодов, в которых исправление ошибок достигается с помощью простых структурных понятий теории кодирования, позволяющих найти комбинации ошибок более прямым путем в отличие от алгебраических методов. Это подтверждает развитие отечественных схем многопорогового декодирования, основанных на итеративных процедурах. Названные методы обеспечили приемлемую сложность декодеров в зависимости от кратности исправляемых в них ошибок. При этом применение оптимальных статистических решений в процедуре мягкого декодирования так же, как и применение стирающего канала связи, обеспечивает дополнительный выигрыш по достоверности.
Вместе с этим, технологические успехи в реализации больших объемов памяти привели к тому, что совсем недавно списочное декодирование полиномиальных кодов стало объектом пристального внимания ряда исследований, показавших возможности таких кодов за пределами их конструктивной корректирующей способности. Это объясняет возрастающий интерес к декодированию блоковых кодов.
В этой связи задача поиска надежных неалгебраических методов декодирования систематических кодов с использованием информации об условиях процедуры демодуляции является актуальной, отвечает перспективам развития телекоммуникационных технологий и служит предметом интенсивных исследований, как в России, так и за рубежом.
Цель работы
Целью работы является разработка и моделирование алгоритмов неалгебраического декодирования систематических кодов с использованием целочисленных индексов достоверности символов, получаемых на основе кортежа стираний.
Для достижения поставленной цели в работе решались следующие задачи:
Проведение сравнительного анализа канонических моделей каналов связи и методов обработки стираний для выработки механизма формирования целочисленных индексов достоверности символов на основе кортежа стертых позиций.
Разработка аналитической модели стирающего канала связи и теоретическое обоснование способа формирования целочисленных индексов достоверности, учитывающего корреляционные зависимости потока информационных символов и стираний.
Создание алгоритма обработки комбинаций систематических кодов с использованием алгебры логарифмических отношений правдоподобий и закономерностей проверочных соотношений, выраженных графом Таннера.
Синтез алгоритма обработки кодовых комбинаций систематических кодов с использованием индексов достоверности и средств кластерного анализа
(списочного декодирования), позволяющего получить характеристики декодера, выходящие за пределы конструктивных корректирующих особенностей систематических кодов.
5. Осуществление программной реализации предложенных алгоритмов и оценка их эффективности методом имитационного моделирования.
Методы исследования
Теоретические исследования, проведенные в диссертации, основаны на применении методов алгебраической теории групп, колец и полей, методов теории вероятностей и теории случайных процессов, теории меры и математической статистики. Экспериментальные исследования проводились с применением методов математического моделирования в среде MATLAB.
Научная новизна исследования
1. Разработана аналитическая модель стирающего канала связи, использующая аппарат дискретных марковских процессов и позволившая найти корреляционную зависимость потока информационных символов и стираний для решения задачи оптимального выбора параметров системы, формирующей целочисленные индексы достоверности символов кодовых комбинаций.
2. Впервые разработан алгоритм адаптивной процедуры плавного изменения интервала стирания в зависимости от характера изменения индексов достоверности, позволяющий повысить достоверность приема информации при низких соотношениях сигнал-шум (патент РФ на изобретение № 2209519).
3. Впервые сформулирован и обоснован способ декодирования
систематических кодов с использованием алгебры логарифмических
отношений правдоподобий и свойств графа Таннера, позволяющий повысить
индексы достоверности информационных бит за счет мощности проверочных
символов (патент РФ на изобретение №2256294).
4. Разработан и научно обоснован новый способ неалгебраического
декодирования кодового вектора за счет разбиения множества разрешенных
кодовых комбинаций на кластеры и представления их в форме созвездий в
декартовой системе координат двумерного евклидова пространства. Рассмотрен оригинальный алгоритм поиска правильного решения на основе анализа защитных зон каждой кодовой комбинации и введения весовых коэффициентов для исправления стертых позиций.
5. Предложен способ обработки информации, позволяющий снизить сложность декодера при исправлении стираний высокой кратности, за счет использования весовых характеристик стертых символов и исключения из анализа тех из них, которые имеют низкие весовые показатели.
Практическая значимость исследования
Изложенный в работе новый метод обработки систематических кодов, способен обеспечить повышение их корректирующих возможностей при низких отношениях сигнал-помеха.
Структура разработанных алгоритмов формирования стираний на основе отображения непрерывного канал связи с последующей процедурой образования потока индексов достоверности символов кодовых комбинаций обеспечивает возможность простой программно-аппаратной реализации цифровых систем обработки информации.
Вышеуказанные результаты работы приняты для практического использования в разработках ФНПЦ ОАО НПО «Марс», в 29 Испытательном полигоне (войск связи) и в 16 Центральном научно-исследовательском испытательном институте связи МО РФ.
Использование результатов работы подтверждено соответствующими актами, находящимися в приложении к диссертационной работе.
Личный вклад автора
Автор лично разрабатывал методики исследований, проводил теоретические расчеты, разрабатывал алгоритмы декодирования и выполнял эксперименты на моделях, осуществлял обработку, анализ и обобщение полученных в ходе исследования результатов.
Достоверность результатов, представленных в диссертации подтверждается корректностью применения математического аппарата,
непротиворечивостью фундаментальным положениям теории информации и общей теории связи, определяется близостью теоретических расчетов и экспериментальных данных, полученных на ЭВМ. Апробация результатов исследования
Основные положения диссертационной работы докладывались и обсуждались на 61-й научной сессии Российского НТОРЭС им. А.С. Попова г. Москва 2006 г.
В трудах 4-й Всероссийской научно-прак. конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем»- Ульяновск: УГТУ, 2004 г.
В трудах IX Военной НТК «Актуальные вопросы совершенствования техники и систем военной связи на основе современных телекоммуникационных технологий» - Ульяновск: 29 ИП МО РФ, 2004.
В трудах Всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем», Ульяновск, УГТУ, 1998.
1.В статье: Декодирование на основе лучших показателей качества приема сигнала // Автоматизация процессов управления, 2004, №1(3), С.43-46, а также в статье: Неалгебраическое декодирование групповых кодов в стирающем канале связи//«Системы и средства связи телевидения и радиовещания», № 1,2, 2006- С 49-55Новизна технических решений закреплена в патентах РФ на изобретения № 2209519 от 27.7.2003 г. и № 2256294 от 10.7.2005 г. Публикации
По теме диссертации опубликовано 10 работ, в том числе 6 статей в сборниках научных трудов и материалов конференций, 1 статья в журнале «Автоматизация процессов управления», 1 статья в журнале «Системы и средства связи, телевидения и радиовещания», входящем в перечень ВАК РФ, и в двух патентах РФ на изобретения.
Положения, выносимые на защиту
1. Получено аналитическое выражение для оценки корреляционной функции
потока информационных символов и стираний, позволяющее
оптимизировать процедуру формирования целочисленных индексов
достоверности символов на основе кортежа стертых позиций.
Предложен и реализован алгоритм применение алгебры логарифмических отношений правдоподобий для систематических кодов, учитывающий особенности двудольных графов Таннера и позволяющий повысить индексы достоверности информационных символов за счет мощности оценок проверочных разрядов.
Разработан способ неалгебраического декодирования систематических кодов за счет разбиений множества разрешенных комбинаций на кластеры и представления их в форме созвездий в декартовой системе координат двумерного евклидова пространства.
Разработан алгоритм поиска правильного решения при декодировании систематических кодов на основе анализа защитных зон каждой кодовой комбинации и введения весовых коэффициентов для исправления стертых символов.
Доказана возможность исправления стираний, кратность которых превышает конструктивную корректирующую способность систематического кода.
Структура и объем диссертации
Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка используемой литературы, включающего 109 работ отечественных и зарубежных авторов и трех приложений. Общий объем диссертации составляет 144 листа.
Модель непрерывного канала связи со случайными характеристиками
Структурная схема цифровой системы связи, приведенная на рисунке 1.1, широко известна и неоднократно обсуждалась во многих фундаментальных работах, посвященных проблеме повышения достоверности цифровых систем обмена информацией или ее хранения [9,22,46,59,63,65,95,107]. Анализ такой системы основывается на понятии математической модели канала связи. В свою очередь, модель трактуется как система с определенными каким-либо образом детерминированными или стохастическими характеристиками, связывающими множества передаваемых и принимаемых сигналов [6].
Сигналы от источника сообщений поступают на вход устройства защиты от ошибок (УЗО), задачей которого является преобразование сообщений, генерируемых источником, в последовательность комбинаций избыточного кода. Преобразования совершаются таким образом, чтобы первоначальное сообщение, переданное по каналу с помехами, было восстановлено приёмной стороной с заданной степенью точности. В ряде случаев УЗО строятся по каскадному принципу и могут содержать несколько кодеров, включенных последовательно или параллельно [75,83]. Выход УЗО передачи подключается к входу устройства преобразования сигналов (УПС). Задачей УПС передачи является преобразование дискретной q- ичной последовательности к виду удобному для передачи на физическом уровне. Приемная сторона осуществляет обратные преобразования. При этом УЗО приема в целях улучшения общих показателей по достоверности может иметь цепь обратной связи для итеративного использования апостериорных оценок декодирования в процедуре обработки кодовых комбинаций [1,40,65]. В зависимости от целей исследования множества входных V и выходных U сигналов могут быть дискретными и тогда рассматривается модель с дискретным каналом. Если множества V и U континуальны, тогда анализу подвергается модель с непрерывным каналом.
Определенная часть современных систем связи реализует двухсторонний информационный обмен, позволяющий использовать алгоритмические методы повышения достоверности. На схеме это отражено двусторонними стрелками между блоками системы. Однако в основе этих методов лежат кодовые методы повышения достоверности, характерные для однонаправленных систем. Их развитие является достаточным условием для совершенствования первых, поэтому в работе рассматриваются только однонаправленные системы обмена данными. Помехи преднамеренного характера (/) показаны на схеме для общности рассуждений. Борьба с ними представляет собой самостоятельную задачу, которая выходит за рамки настоящей работы.
Математически непрерывный канал определяется совокупностью множества передаваемых сигналов V, множества принимаемых сигналов U и условного распределения вероятностей Л /v) IeB, veV, заданного на некоторых подмножествах множества U. Здесь множество В - а -алгебра борелевского множества U [46,55,75]. В большинстве моделей систем связи из непрерывного множества V выделяется дискретное подмножество разрешенных сигналов и сигналы, не входящие в него, считаются запрещенными. В ряде работ подобная структура интерпретируется как полунепрерывный канал, а процедура декодирования в них как канал со стираниями элементов или канальными измерениями [22,41,74]. На схеме (рисунок 1.1) сигналы стирания обозначены через Sy, а символы, сопровождаемые оценками канальных измерений, обозначены через Sj.
Свойства оценок Sj и Sj однозначно зависят от потенциальных возможностей непрерывного канала и изучение его особенностей, в этой связи, прямо отвечает целям проводимых исследований.
Наиболее простой моделью непрерывного канала является неискажающий канал с аддитивной помехой [5,12,18,21,51]. В ней V и U - множества функций непрерывного или дискретного времени t, заданные на некотором интервале Т. Выходной сигнал u{t) в модели представляет собой сумму входного сигнала v(/) и случайного процесса «(/), отражающего некоторые закономерности мешающих факторов: u(t) = v(t) + n(t). (1.2.1) Свойства такого канала могут быть подчеркнуты определенным образом за счет введения коэффициентов ju и г, которые соответствуют коэффициенту передачи канала и задержке, тогда u(t) = ju-v(t-r)+n(t). (1.2.2)
Если n{t) - гауссовский процесс, то модель отражает свойства канала с аддитивной гауссовской помехой. Дальнейшее совершенствование модели связывается со свойствами среды распространения сигнала. В случае оптоволоконных или кабельных каналов оправдано использование линейного преобразования вида L, непрерывного в пространстве V.
Функции правдоподобия для двоичного симметричного канала связи
В большинстве реальных систем связи передаваемый сигнал имеет память (сигналы, переданные на последовательных сигнальных интервалах оказываются между собой зависимы). Оптимальная решающая схема должна учитывать эту зависимость. Детектор, который основывает свои решения на наблюдении последовательности принимаемых сигналов следующих на последовательных сигнальных интервалах отвечает таким требованиям [62]. Алгоритмы такого рода делятся на две класса. В одном - реализуется алгоритм максимального правдоподобия для детектирования последовательности символов, определяющий минимум евклидова расстояния траекторий (путей на решетке, которая характеризует память переданного сигнала). В этом случае по заданной последовательности и={и ;и ;...;и } на выходе согласованного фильтра или корреляционного демодулятора детектор определяет последовательность 3= {8,;„;...; }. 12 п
Такой детектор получил название максимально правдоподобный последовательный детектор. Он выбирает последовательность д, которая минимизирует евклидово расстояние N D{u,d)= {u-5) n n (1.3.7) и=1
Мягкие решения при этом могут быть организованы по принципу, показанному на рисунке 1.5. На этом рисунке (относительно рисунков, приведенных выше) измены значения -1 на 0, а +1 на 1. Правдоподобие О p(S\0) Правдоподобие 000 001 010 011 100 101 ПО 111. 8-уровневая схема мягких решений -А J V о V 2-уровневая схема жестких решений
Рисунок 1.5 - Жесткая и мягкая схемы декодирования Это позволяет представить алгоритм Витерби на плоскости квадрата со стороной равной 7 единицам, у которого в начале координат размещается значение 0, значение 7 размещается в точке А(7;7). В этом случае для случайной точки, попавшей на плоскость квадрата, расстояние до начала координат и до точки А определяется по метрике Евклида. Мягкое декодирование для непрерывных кодов по алгоритму Витерби определяется так же, как и жесткое декодирование, стой лишь разницей, что в этом случае вместо метрики Хэмминга используется метрика Евклида, как показано на рисунке 1.6. о, о 7, о
Рисунок 1.6 - Декодирование по Витерби в метрике Евклида В другом классе посимвольное решение выносится по правилу максимума апостериорной вероятности, основанное на наблюдении последовательности сигнальных интервалов. Такой алгоритм был разработан для борьбы с межсимвольной интерференцией. В общем, рекуррентный алгоритм для детектирования символа 8 после приема некоторой последовательности длиной D символов и ,и ,...,и можно записать в виде D S = avg{maxр(и ,и ,...,u\S)P(dn)} = arg{maxZ---Hp (и ,-..«")} 5 5 uD ип Как отмечено в [62] основная проблема этого алгоритма вычислительная сложность для многоуровневых сигналов. Для двоичных систем этот алгоритм реализуется относительно просто.
Способ получения оценок надежности символов в стирающем канале связи
В работе [67,68] предлагается метод получения оценок надежности принятых символов на основе потока стираний. В этой концепции считается, что между символами существует корреляционная зависимость. Функция корреляции, как обычно - четная. Для определения оценки надежности символа назначаются два скользящих окна размерами Кх и К2 бит каждое, при этом К1=К2. Совместный поток информационных символов и поток стираний разделяются. В потоке стираний не стертым в первичной последовательности информационным символам присваивается значение ноль, а стертым позициям присваивается значение единица. Окна следуют по выделенной из потока данных последовательности стираний одно за другим, перекрываясь между собой, на интервале одного бита. Оценка надежности вырабатывается для бита, попавшего в оба окна по принципу подсчета числа стираний в окнах К{ и К2.
Первоначально каждому окну присваивается вес Кх+\ и К2+1. Если в окно попало S стираний, то вес окна уменьшается на эту величину. Общая оценка определяется как сумма оценок первого и второго окна: R = (Ki-S]+\) + (K2-S2+\). ( 1.3.8) Пусть на приемной стороне образовалась последовательность символов пронумерованная относительно анализируемого символа xt по оси времени влево и вправо: Л Л Л Л Л Л А Л/+3 Л/+2 Л/+1 Л/ Л/-1 Л/-2 Л/-3 Тогда в окно при К{= 3 попадают символы xt ,xt_i ,xt_2, а в окно К2 символы Xt+2 ,xt+2 ,Xt. Минимальной оценкой для х( в указанных условиях, в соответствии с (1.1.1), оказывается оценка 2 (все символы в окнах стерты и равны единицам), а максимальной оценкой может служить оценка 8 (все символы в окнах равны нулю). Легко убедиться в том, что оценки меньшего веса совпадают со стираниями и в силу этого могут служить оценками достоверности для принятых символов. После оценки символа xt, при получении очередного значения xt+4, приемник сдвигает окна влево на символ xt+i и оценивает его описанным способом, символ х(_2 на этом шаге из анализируемой последовательности удаляется.
Модель марковского двоичного канала со стираниями
В 1.2 показано, что не все каналы связи могут быть описаны процессами гауссовского характера. В таких случаях дискретный канал как отражение непрерывного канала, представляют в виде марковского процесса. Основной причиной построения таких моделей является стремление отойти от сложной природы образования ошибок в непрерывном канале связи и их коррелированности с мешающими факторами. Например, представляя каналы с импульсными помехами в виде каналов с кратковременными прерываниями, удобно моделировать такие системы именно марковскими процессами. Для таких процессов относительно просто получить корреляционные зависимости, которые могут быть использованы при формировании индексов достоверности символов. В п.2.2 главы теоретически обоснованы размеры окон для получения указанных индексов.
Природа импульсных помех достаточно хорошо описана в ряде источников в форме аналитических моделей, однако поведение стирающего канала связи при таком виде помех изучена недостаточно. В большой степени это связано с тем, что основным методом борьбы с импульсными помехами различной интенсивности является своевременное их обнаружение и последующее отключение канала связи от приемника информации. В п.2.3 оценивается эффективность стирающего канала в условиях применения фазовой модуляции.
В п.2.4 доказывается возможность применения модели марковского типа для изучения особенностей потока стираний и ошибок, которые важны для выбора алгоритмов функционирования декодирующих устройств и осуществления граничных оценок, проводимых в п.2.5.
Во многих практически важных приложениях, например, в мобильной связи, предъявляются повышенные требования к стоимости декодера. Часто декодер представляет собой интегральную схему, размещенную в одном чипе. Важную роль играют так же надежность в эксплуатации и минимальная мощность принимаемого сигнала. В связи с указанными требованиями необходимо снижать их сложность с минимальными потерями эффективности, при этом, особую роль играют целочисленное представление метрики и простота арифметических операций декодирования.
Возможность получения целочисленных оценок надежности символов в стирающем канале связи впервые на эмпирическом уровне была предложена в [65] и не имела строгого теоретического обоснования с точки зрения корреляционных связей между оцениваемыми символами. Модель гауссовского канала описывает поток независимых бит и стираний, поэтому обоснование метода целесообразно провести на основе изучения функции корреляции дискретного марковского процесса.
Пусть процесс 6(t) в любой момент времени может принимать лишь три значения: и =+1, при условии, что фиксируется непосредственно значение +1 или значение в интервале от +1 до +р/2; i 2=0, если реализация процесса оказалась в пределах интервала р (здесь р- характеризует ширину интервала стирания, при этом 0 /? 1), а Щ характеризует значение -1. Параметр р целесообразно связать с вероятностью ошибки в канале связи, предположив, что рассматривается чисто стирающий канал связи. Будем считать, что вероятность перехода +1-»-1 за малое время At равна AAt, а вероятность перехода -1-»+1 равна jiAt. Обозначим вероятность перехода из состояния +1 в зону стирания за время At или из состояния -1 в ту же зону через pAt. Пусть для такого процесса известны вероятности начального состояния р\ = Р{в(і0) = +l}, р2 = P{0(to) = О} и pi = P{&(t0) = -і}. Определим вероятности перехода л: (tQ,t) = P (t) = u #( ) = ,} (гДе t;j=+l, t 2=0 Vi 1- -» »У = 1 3), здесь #/.( 0,0 условные вероятности нахождения системы в состоянии и. в момент времени /, если известно, что в предшествующий момент времени /Q она находилась в состоянии v.. Если принять р = 0, то канала вырождается в двоичный канал и описывается марковским процессом с двумя состояниями. Если параметр р 0 и составляет долю интервала от +1 до -1, то вероятности перехода XAt и fiAt изменятся пропорционально принятому значению р. При р = 1 канал не имеет смысла, поскольку вырождается в чисто стирающий. Условие нормировки процесса определяется выражением
Обычно [68] вероятности перехода из одного состояния в другое неотрицательны (a,.(t) 0). С учетом условий нормировки (2.2.1) получаем, что ам(0 = X akj(0-Q Переходя к пределу при At- О, для JU k) стирающего канала с тремя состояниями получим систему линейных дифференциальных уравнений д 3 — - ,j{t0,t) = I akJ(t)7T.k(t0,t), і J = 1,3 (2.2.2) К—1 В случае разрывных марковских процессов для малых временных интервалов At и / = 1 вероятности перехода a..(t,t + At) примут вид: а 2= р, а -Х- — . Отсюда находим а j = -(Л + —). Так как все коэффициента а.. 2 2 J постоянные величины, не зависящие от времени, то процесс 6{t) является однородным. Аналогично для і = 2 получаем: а2і Pt а2Ъ Р и а22 = Р Для / = 3 значения a.(t,t + At) будут иметь вид: а \-Р- » й32 = Р и
Кластерный подход к декодированию полиномиальных кодов
Неалгебраические методы декодирования систематических кодов в сочетании с мягкой обработкой сигналов показали свое преимущество перед классическими методами. Именно к таким методам следует отнести, прежде всего, приемы списочного декодирования, которые были введены Элайесом и Возенкрафтом. Списочное декодирование кодов Рида-Соломона стало объектом пристального внимания, вызванного рядом публикаций, указывающих на возможности таких кодов реализовать корректирующие способности за пределами их конструктивной способности.
В разделе 3.2 развивается подход, при котором множество кодовых комбинаций двоичного кода по специфическим признакам разбивается на кластеры. Принятый кодовый вектор отождествляется с одним из них и из списка кодовых комбинаций выделенного кластера и по дополнительным признакам выделяется последовательность информационных символов. Исследуется возможность коррекции стираний при таком подходе, оцениваются свойства кодов при исправлении стираний в выделенной группе, доказывается ряд утверждений, позволяющих разработать патентно чистые алгоритмы исправления стираний большой кратности.
В разделе 3.3 разрабатывается алгоритм обработки кодовых комбинаций с использованием алгебры логарифмических отношений правдоподобий и свойств двудольного графа Таннера. Данный алгоритм играет важную роль при реализации процедуры декодирования по списку.
В разделе 3.4 обсуждаются вопросы параметрического и структурного синтеза мягкого декодера групповых кодов, использующего оценки достоверности символов, выработанных на основе кортежа стираний.
Решение проблемы декодирования блочных кодов алгебраическими методами, опирающихся на критерий максимума правдоподобия и метрику Хэмминга натолкнулась на проблему сложности декодера, исправляющего от трех и более ошибок. После указанного порога, трудности технической реализации декодера возрастают экспоненциально относительно кратности исправляемых ошибок. Это привело к созданию неалгебраических методов исправления ошибок, построению каскадных схем кодирования -декодирования с последовательным включением декодеров и схем турбо кодирования с параллельным включением декодеров.
Списочное декодирование (т.е. выдача списка возможных решений декодера) было введено Элайесом и Возенкрафтом [86]. Совсем недавно списочное декодирование полиномиальных кодов стало объектом пристального внимания, вызванного главным образом публикациями Судана и его коллег [107] о декодировании кодов PC за пределами их конструктивной корректирующей способности. Предложенный ими метод, который называют алгоритмом Судана, использует интерполяцию и факторизацию многочленов двух переменных над расширением базового поля. Алгоритм Судана можно рассматривать как развитие алгоритма Берлекэмпа - Велча [84]. Этот алгоритм был применен для декодирования с мягким решение кодов PC [96].
Суть рассматриваемого в работе способа обработки кодовых векторов заключается в том, что все множество разрешенных комбинаций блокового кода разбивается на подмножества (кластеры), определяемые по заранее оговоренном принципу, с последующим определением принятого вектора по метрике Евклида внутри кластера. Для этого символы кодовой комбинации разбиваются на две группы, каждая из которых образуют координаты по двум осям координатной плоскости. Такое разбиение приводит к размещению разрешенных комбинаций кода в трехмерном пространстве, при этом номера кластеров образуют плоскости, для которых известны координаты кодовых векторов, принадлежащие данному кластеру. Применение на практике данного метода требует доказательства ряда утверждений, основанных на алгебраической теории групп, колец и полей.
Утверждение 1. Если число двоичных символов, определяющих признак кластера равно / и 0 f k, где к - число информационных символов в кодовом векторе циклического кода, то число комбинаций такого кода, входящих в кластер одного признака, определяется соотношением 2k f. При / = 0 все кодовые векторы входят в один кластер (система алгебраического декодирования).
Доказательство: пусть общее число комбинаций группового кода равно 2 . Из любого циклического кода путем регулярных преобразований или линейных преобразований над строками порождающей матрицы G можно образовать систематический код с матрицей G = [1 :Р], порождающей тот же код. В единичной матрице Ik всегда можно выделить единичную матрицу меньшей размерности /, где \ f k. Путем линейных преобразований над строками выделенной матрицы 1}, можно получить двоичное поле Галуа степени расширения /, при этом комбинации поля GF{2f) будут определять признак кластера или его номер. Поле GF{2f) содержится в поле GF(2 ) ровно 2 -/ раз, следовательно, число кодовых комбинаций в одном кластере будет определяться этим же соотношением. Утверждение доказано.
