Методы и устройства помехоустойчивой радиосвязи

Федеральное агентство связи Российской Федерации СибГУТИ С.В. Воробьева методы и устройства Помехоустойчивой радиосвязи Конспект лекций Новосибирск – 2017 ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ 3 Глава 1 ПРИНЦИП ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ 4 1.1 Роль и место помехоустойчивого кодирования в системах телекоммуникаций 4 1.2 Дискретный канал связи 6 1.3 Основные понятия и определения теории кодирования 7 1.4 Кодирование и декодирование 8 1.5 Классификация помехоустойчивых кодов 13 1.6 Спектр весов кода. Кодовые границы 13 1.7 Вероятностные характеристики некоторых кодов 17 1.7.1 Код с четным числом единиц 17 1.7.2 Код с постоянным весом 18 1.7.3 Инверсный код 18 1.7.4 Блочный код (23,12) 19 1.8 Энергетический выигрыш от кодирования 20 Глава 2 ГРУППОВЫЕ КОДЫ 21 2.1 Групповые линейные коды 21 2.2 Коды Хэмминга 28 Глава 3 ЦИКЛИЧЕСКИЕ КОДЫ 30 3.1 Циклические коды и их свойства 30 3.2 Коды Боуза–Чоудхури–Хоквингема 33 3.3 Декодирование циклических кодов 35 3.4 Субоптимальные методы декодирования циклических кодов 43 3.4.1 Перестановочные методы 43 3.4.2 Мажоритарное и пороговое декодирование 45 Глава 4 АЛГЕБРАИЧЕСКОЕ ДЕКОДИРОВАНИЕ КОДОВ БЧХ 47 4.1 Недвоичные циклические коды БЧХ 47 4.1.1 Коды Рида-Соломона 47 4.1.2 Декодер кода РС с вылавливанием ошибок 51 Глава 5 СВЕРТОЧНЫЕ КОДЫ 53 5.1 Сверточные коды и их свойства 53 5.2 Кодирование и декодирование сверточных кодов 57 5.2.1 Методы кодирования и декодирования 57 5.2.2 Декодирование по алгоритму Витерби 63 5.2.3 Последовательное декодирование 68 5.2.4 Пороговое декодирование сверточных кодов 71 Глава 6 КАСКАДНЫЕ КОДЫ 84 6.1 Последовательные каскадные коды 84 6.2 Параллельные каскадные коды 87 БИБЛИОГРАФИЯ 105 ПРЕДИСЛОВИЕ Современные сети и системы передачи информации охватывают все стороны деятельности человека. В системах связи стали передавать цифровые сигналы с более высокими требованиями к достоверности передаваемой информации [1], а удовлетворить этим требованиям совершенствованием линий связи, увеличением излучаемой мощности, снижением собственного шума приемных устройств зачастую оказывается экономически невыгодно или же просто невозможно. В соответствии с теоремой Шеннона для дискретных каналов связи (ДКС) с помехами информация в таких каналах может передаваться со сколь угодно высокой степенью достоверности при условии, что скорость передачи информации не превышает пропускной способности канала. Помехоустойчивость (достоверность), как известно, определяется способностью системы противостоять вредному влиянию помех или, другими словами, это способность системы связи функционировать с требуемым качеством в условиях неблагоприятных внутренних и внешних воздействий. Количественной мерой помехоустойчивости при передаче дискретных сообщений, как правило, является вероятность ошибки в принимаемой последовательности. Основным средством обеспечения высокой помехоустойчивости является контролируемое введение избыточности, необходимой для обнаружения и исправления ошибок, возникающих при работе системы и ее элементов. Теоретической базой эффективного использования вводимой избыточности является теория помехоустойчивого кодирования. Помехоустойчивые (или корректирующие) коды имеют различные приложения. Так эти коды используются для защиты данных от ошибок в вычислительных устройствах и сетях, системах хранения данных, спутниковых и навигационных системах, в системах сотовой связи; коды могут быть использованы для получения надежной связи даже тогда, когда мощность принимаемого сигнала близка к мощности шумов. В специальных приложениях коды используются для защиты информации против преднамеренно организованных помех. Глава 1 ПРИНЦИП ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ 1.1 Роль и место помехоустойчивого кодирования в системах телекоммуникаций Система связи соединяет источник данных с получателем посредством канала связи. Структурная схема системы связи изображена на рисунке 1.1. Рисунок 1.1 – Обобщенная структурная схема системы связи Статистическое кодирование используется для уменьшения первичной избыточности передаваемой информации. Для описания этого процесса широко используется понятие “сжатие данных”. В зависимости от области применения различают два основных типа схем сжатия: 1) «Без потерь информации» – коды Шеннона–Фано, Хаффмана, арифметическое кодирование, коды Лемпела–Зива (используемые, например, при архивировании данных в ЭВМ – архиваторы Zip, Rar и др.); 2) «С потерями информации» – кодирование с преобразованием и оценкой движения (например, сжатие статических изображений и видео). Криптографическая защита используется для предотвращения несанкционированного доступа к информации. Широкое применение нашли системы криптографической защиты в среде Интернет (финансовые операции и операции аутентификации пользователей), в различных программных продуктах (операционные системы и программные приложения) и др. Архиватор Rar использует шифрование, Zip – нет. Популярный формат электронных документов pdf (portable document format), предназначенный для межмашинного обмена готовыми документами и используемый в издательствах, также использует шифрование (в отличие от аналогичного формата ps – post script). Следует отметить, что шифрование наиболее эффективно при работе с данными, имеющими малую избыточность, поэтому используется предварительное сжатие данных. Помехоустойчивое кодирование предназначено для защиты данных от ошибок и применяется в системах передачи и хранения данных либо только для обнаружения ошибок, либо для обнаружения и исправления ошибок (или ошибок и стираний в каналах со стиранием). Последовательность действий при передаче дискретных сообщений может быть пояснена следующим образом. Поток данных, поступающих на вход кодера помехоустойчивого кода (кодер ПК), преобразуется в новый поток данных путем разбиения на кодируемые группы и добавления избыточности, необходимой для борьбы с помехами, имеющими место в канале связи. Основная задача перемежителя состоит в перестановке элементов потока данных с выхода кодера помехоустойчивого кода таким образом, чтобы деперемежитель на приемной стороне декоррелировал помехи, т.е. преобразовал пакет ошибок, происходящих в реальных дискретных каналах связи (ДКС) в поток независимых ошибок. Модулятор преобразует кодовые символы с выхода перемежителя в соответствующие аналоговые символы. Так как в канале связи возникают различного типа шумы, искажения и интерференция, то сигнал на входе демодулятора (первое решающее устройство) отличается от сигнала на входе модулятора. При этом сигнал на выходе демодулятора является оценкой соответствующего переданного символа, а из-за шумов в канале возникают ошибки. В зависимости от характера оценки доверия к сигналу на выходе демодулятора различают мягкое и жесткое решения. В соответствии с правилом жесткого решения сигнал на выходе демодулятора определен однозначно для каждого тактового интервала (“0” или “1” для двоичного канала). Демодулятор с мягким решением обычно имеет два выхода: один из них представляет собой жесткое решение, на втором выходе формируется оценка качества этого решения в виде веса wi, пропорционального отношению правдоподобия на выходе демодулятора. Мягкое решение демодулятора может быть использовано для дальнейшего повышения помехоустойчивости приема (например, мягкого декодирования кодовых слов помехоустойчивого кода). Наиболее часто используются 8-и или 16-и уровневые оценки качества (3 или 4 двоичных символа, [2,3]). Декодер помехоустойчивого кода (второе решающее устройство) использует избыточность кодового слова для того, чтобы обнаружить или обнаружить и исправить ошибки в принятом слове, и затем выдает оценку кодового слова источника сигнала потребителю. Если все ошибки исправлены, то оценка кодового слова совпадает с исходным кодовым словом источника, следовательно, информация достигла получателя без искажений. Основные практические приложения теории помехоустойчивого кодирования включают (но не ограничиваются): • Сотовая, транкинговая, пейджинговая и спутниковая связь; • Сети передачи данных (Ethernet, Wi-Fi, Bluetooth – как правило, коды используются в режиме обнаружения ошибок); • Модемы (протоколы V.32/V.90 используют решетчатое кодирование, V.42 – кодирование с обнаружением ошибок и переспросами); • ОЗУ ЭВМ (в режиме обнаружения или в режиме исправления); • Шины данных ЭВМ (USB и др., высокая скорость кода, малая избыточность); • Магнитные и оптические носители информации (Minidisks, CD, DVD) и мн.др. 1.2 Дискретный канал связи Если входные и выходные сигналы канала являются дискретными, то и канал называется дискретным (ДКС). На рисунке 1.2 приведена обобщенная структурная схема системы передачи дискретных сообщений (СПДС). Рисунок 1.2 – Обобщенная структурная схема СПДС Математическая модель ДКС требует описания следующих параметров: 1) алфавитов входных и выходных сообщений; 2) скорости передачи элементов алфавита; 3) переходных вероятностей. Диаграмма состояний и переходов для двоичного дискретного канала связи со стираниями показана на рисунке 1.3, где S0, S1 – элементы алфавита источника; y0, y1 – элементы алфавита на выходе канала; q – символ стирания; p(yi /Sj) и p(q /Sj) – переходные вероятности, где i, j  {0, 1}. Рисунок 1.3 – Диаграмма состояний и переходов для двоичного ДКС Характеристики непрерывного канала (в том числе характер действия помех в линии связи) проявляются в свойствах переходных вероятностей ДКС. В результате этого ДКС могут быть [4]: 1) симметричными, когда переходные вероятности p(yi /Sj) одинаковы для всех ij и, соответственно, несимметричными в противном случае; 2) без памяти, когда переходные вероятности p(yi /Sj) не зависят от того, какие символа и с каким качеством передавались до данного символа Sj, и с памятью в противном случае; 3) без стирания, когда алфавиты на входе канала и выходе демодулятора совпадают, в канале со стиранием алфавит на выходе демодулятора имеет дополнительный символ стирания q, формируемый тогда, когда демодулятор не может с заданной надежностью опознать переданный символ. Ошибки в симметричных каналах без памяти независимы и характеризуются вероятностью ошибки p – примером является биномиальный канал. В каналах с памятью ошибки пакетируются (группируются) – примером является марковский канал, см. главу 7. 1.3 Основные понятия и определения теории кодирования Избыточность кода , (1.1) где n – количество элементов (символов) в кодовом слове; k и r – количество информационных и проверочных символов, соответственно. Скорость кода . (1.2) Чем больше избыточность кода, тем меньше скорость кода, и наоборот. Расстояние Хэмминга между двумя кодовыми словами dij , (1.3) где , – координаты слов, в n-мерном неевклидовом пространстве. Если код является двоичным, под расстоянием между парой кодовых слов понимается количество символов, в которых они отличаются между собой. Оно определяется сложением этих двух слов по mod 2 и равно числу единиц в этой сумме dij=[(Ai+Aj)mod 2] “1”, (1.4) где (..+..)mod 2 – сложение по mod 2; ∑ “1” – означает, что после операции сложения по модулю два необходимо подсчитать количество единиц в полученном результате. Пример 1.1 Дано: А1=111, А2=100 Решение: d12 =(А1+А2)mod 2= 111 100 011, ∑"1"=2. Ответ: d12 = 2. Таким образом, расстоянием Хэмминга между двумя двоичными последовательностями, называется число позиций, в которых они различны. Минимальное расстояние Хэмминга называться кодовым расстоянием d = min dij. (1.5) Обнаруживающая и исправляющая способности корректирующих кодов тесно связаны с расстояниями между разрешенными кодовыми словами. Число ошибочных символов в принятом кодовом слове называется кратностью ошибки t, при длине кодового слова n символов она изменяется в пределах от 0 до n. Так как кратность ошибки t в геометрическом представлении является расстоянием между переданным словом и принятым, то для обнаружения ошибок кратности tо требуется кодовое расстояние . (1.6) Для исправления ошибок кратности tи, требуется кодовое расстояние . (1.7) Это означает, что для исправления ошибок искаженное кодовое слово должно располагаться ближе всего к соответствующему правильному слову. Кратность исправления tи определяет границу гарантированного исправления ошибок. В случае исправления tи ошибок и tq стираний (кратность стирания) кодовое расстояние d . (1.8) 1.4 Кодирование и декодирование Геометрической моделью n-символьного двоичного кода является n-мерный куб, с ребром, равным единице, каждая вершина которого представляет одно из возможных кодовых слов. Расстояние Хэмминга, таким образом, равно числу ребер такого куба, отделяющих одну вершину от другой. Рассмотрим возможность обнаружения и исправления ошибок на примере передачи двух сообщений с различным количеством символов. А) Возможно два исхода: передается либо единичный, либо нулевой элемент. Так как отсутствует дополнительная информация, то обнаружение и исправление ошибок невозможно, т.е. , . Б) В этом варианте на выходе канала возможны четыре исхода, два из которых позволяют обнаружить ошибки, однако исправить их невозможно, так как количество ребер такого графа, ведущее и разрешенной вершины одинаково, т.е. , . В) В этом варианте возможны восемь исходов, шесть из которых позволяют обнаруживать ошибки и делают возможным исправление одиночных ошибок, так как , , R = 1 / 3. Г) По сравнению с вариантом В количество разрешенных кодовых слов увеличилось в два раза, однако так как все запрещенные слова находятся на границе разделения подмножеств разрешенных слов, то исправление ошибок невозможно. Таким образом, уменьшая избыточность кода фиксированной длины n, можно увеличить скорость кодирования R, однако ухудшаются его обнаруживающая и исправляющая способность. Для примера Г сказанное соответствует: , следовательно , однако (66%). При выборе избыточности, выборе того или иного кода всегда необходимо учитывать характер решаемой задачи: каковы ошибки (зависимые или независимые), ошибки какой кратности и с какой вероятностью происходят в канале связи. Очевидно, что, если в канале связи преобладают ошибки малой кратности, то целесообразно использовать коды с малой избыточностью. Следовательно, необходимо согласование свойств ДСК и параметров помехоустойчивого кода, предназначаемого для борьбы с ошибками в этом канале. При этом скорость передачи сообщений, закодированных помехозащитным кодом, снижается. Так, например, если избыточность составляет (или 25%), тогда скорость кода (75%). В примере, приведенном на рисунке 1.4, указанная избыточность имеет место в результате добавления одного проверочного символа к трем информационным. Рисунок 1.4 – Принцип образования кодового слова Кодер преобразует информационное слово длины k в кодовое слово длины n  k. Если обозначить оператор преобразования через , то кодовое слово A на выходе кодера и информационное слово U на его входе связаны соотношением A=(U). Оператор  может быть задан таблицей соответствия или производящей (порождающей) матрицей. Пример 1.2 Дано: Закодировать двоичным (n, k) кодом, n=6 и k=3, информационные слова u1(010), u2(001), u3(110), u4(111), используя производящую матрицу . Решение: Процесс кодирования в линейном коде сводится к умножению информационных слов на производящую матрицу по правилам умножения матриц и суммирования по модулю 2. A1= u1∙G =0∙(101110)+1∙(010111)+0∙(001011) = 010111, A2= u2∙G =0∙(101110)+0∙(010111)+1∙(001011) = 001011, A3= u3∙G =1∙(101110)+1∙(010111)+0∙(001011) = 111001, A4= u4∙G =1∙(101110)+1∙(010111)+1∙(001011) = 110010. Кодовые слова Ai поступают в канал связи, где подвергаются действию случайных помех. На выходе канала (после демодулятора) получается оценка этого слова . Задачу помехоустойчивого кодирования можно сформулировать как преобразование сообщения источника в передаваемый по каналу связи сигнал, при котором обеспечивается максимум взаимной информации источника и получателя, что достигается за счет избыточности, вводимой для борьбы с помехами. Процесс декодирования можно представить в виде двух операций, в результате которых на выходе декодера получается оценка переданного информационного слова , (1.9) где – операция нейтрализации случайного действия помех в канале; – операция декодирования. Если , то информационные символы в кодовом слове имеют такой же вид, какой они имели на входе кодера (систематический кодер). Оператор является статистическим и должен действовать так, чтобы в соответствии с выбранной мерой качества и критерием оптимальности обеспечивался минимум потерь информации в процессе преобразования полученной оценки в кодовое слово на выходе. Критерием, позволяющим минимизировать потери информации, является критерий максимального правдоподобия (МП). Правило решения по критерию МП можно записать в виде: (1.10) где  и 0 – отношение правдоподобия и пороговое отношение правдоподобия; и – функции правдоподобия (условные вероятности получения кодового слова при передаче кодовых слов Ai и Aj, j i). При этом обеспечивается минимум потерь информации, т.е. I(Ai) - I(Aj) > 0 для всех (1.11) где I(Ai), I(Aj) – взаимная информация кодовых слов и Ai, и Aj. При известных априорных вероятностях Р(Aj) и Р(Ai) иногда используется критерий максимальной апостериорной вероятности (МАВ), минимизирующий среднюю вероятность ошибки декодирования pд= ; i, j=1, 2, …, N, (1.12) где N – число кодовых слов данного кода; P(Ai, Aj) – совместная вероятность передачи кодового слова Ai и принятия решения Aj. Для критерия максимума апостериорной вероятности (МАВ) пороговое отношение правдоподобия в правиле решения (1.10) принимает значение 0 =, (1.13) где P(Ai) и P(Aj)- априорные вероятности передачи кодовых слов Ai и Aj Прежде, чем начать рассмотрение специальных корректирующих кодов, следует отметить, что любой код способен обнаруживать и исправлять ошибки, если не все кодовые слова этого кода используются для передачи сообщений. Наглядным является рассмотрение этого на примере блочных кодов, когда последовательность символов на выходе источника разбивается на блоки (кодовые слова или кодовые комбинации), содержащие одинаковое число символов k. При этом для двоичного кода ансамбль сообщений будет иметь объем Nр=2k. При помехоустойчивом кодировании это множество из Nр сообщений отображается на множество N = 2n возможных кодовых слов, такая процедура и называется помехоустойчивым кодированием дискретных сообщений (n – число символов в кодовом слове после кодирования, иногда его называют длиной кодовых слов или значностью кода). В общем случае для равномерного блочного кода с основанием q код имеет возможных кодовых слов. Используемые для передачи сообщений кодовые слова из множества называют разрешенными, остальные кодовые слова из множества не используются и называются запрещенными (неразрешенными для передачи) [5]. Сущность обнаружения ошибок поясняется на рисунке 1.5а. Если в результате искажений в канале связи переданное кодовое слово Ai (i = 1, 2, … Nр) превращается в одно из запрещенных слов Bj (j = 1, 2, … Nз), то ошибка обнаруживается, так как такое слово не могло быть передано. Ошибка не обнаруживается только в том случае, когда очередное передаваемое кодовое слово превращается в другое разрешенное, например Aj, которое также могло быть передано. По сравнению с обнаружением ошибок исправление ошибок представляет собой более сложную операцию, поскольку в этом случае помимо обнаружения наличия ошибки в принятом кодовом слове необходимо определить местоположение искаженного кодового символа и значение ошибки (для недвоичных кодов). Чтобы рассматриваемый код исправлял ошибки, необходимо часть или все множество запрещенных кодовых слов разбить на Nр непересекающихся подмножеств (i) (i= 1, 2, … Nр) по количеству разрешенных кодовых слов. Каждое из подмножеств (i) в декодере приемника приписывается одному из разрешенных кодовых слов (рисунок 1.5б). Рисунок 1.5  Обнаружение и исправление ошибок Способ приема заключается в следующем. Если принятое кодовое слово принадлежит подмножеству (i), то переданным считается разрешенное кодовое слово . Ошибка не может быть исправлена (исправляется неверно), если переданное кодовое слово в результате искажений превращается в кодовое слово любого другого подмножества (j), (j i). На рисунке 1.5б ошибка в запрещенном кодовом слове B1j будет исправлена, так как это слово принадлежит подмножеству (1), переданного разрешенного слова A1; ошибка в кодовых словах B2j или B4j не будет исправлена, так как эти слова относятся к подмножествам других разрешенных кодовых слов. Если принятое кодовое слово попадает в подмножество запрещенных слов, не принадлежащих ни к одному из подмножеств (i) (i= 1, 2, … Nр), то ошибка только обнаруживается, но не исправляется. Этот признак может быть использован для исправления ошибки другими методами, например, методом переспроса. 1.5 Классификация помехоустойчивых кодов В настоящее время известно большое количество кодов, отличающихся по помехоустойчивости и способам построения. Применение некоторых из них ограничивается сложностью технической реализации кодеков (объединенное название кодера и декодера). Рассмотрим классификацию кодов, наиболее часто используемых на практике. Двоичные и недвоичные коды отличаются друг от друга основанием кода m; если m>2, то код является недвоичным (соответственно, троичным, четверичным и т.д.). Линейные коды – коды, у которых избыточные символы образуются в результате линейных операций над информационными символами. Большинство используемых на практике помехоустойчивых кодов являются линейными (циклические, сверточные и др.), так как они относительно просто кодируются и декодируются. Нелинейные коды (с постоянным весом, инверсные и некоторые другие) в сравнении с линейными имеют малую длину кодовых слов и используются, в основном, в специальных приложениях, так как часто обеспечивают лучшие параметры. Систематические коды – такие коды, у которых информационные символы не кодируются и на выходе кодера имеют такой же вид, как и на его входе. У блочных кодов в отличие от непрерывных последовательность кодовых символов на выходе кодера делится на кодовые слова (блоки), в декодере каждое слово из n символов декодируется отдельно. Каскадные коды образуются параллельным или последовательным включением нескольких помехоустойчивых кодов. 1.6 Спектр весов кода. Кодовые границы Кодовое расстояние – это минимальное расстояние между кодовыми словами, находимое, при использовании двоичных кодов, сложением по модулю два и суммированием всех единиц. d = min d(Ai, Aj). (1.14) Спектр весов кода N(w) – это множество расстояний ненулевых слов данного кода от нулевого слова, где w=[1, n] – веса этих слов. Пример 1.3 Дано: А=(0,0,0,0,0,0,0); А=(1,0,1,1,0,0,0). Решение: Аналогично примеру 1.1. Ответ: w=d0j=3. Следует иметь в виду, что: используемых (разрешенных) кодовых слов. Для нахождения спектра весов кода (СВК), широко используется понятие производящая функция спектра весов кода . Производная порядка w от T(z) по zw равна , откуда можно получить границу Чернова для СВК . (1.15) Граница Чернова показывает минимальное количество кодовых слов, находящихся на расстоянии w от нулевого слова, и позволяет найти спектр весов данного кода по производящей функции. Эта граница определяет, по-сути, значение кодового расстояния для wmin. Пример 1.4 Дано: Помехоустойчивый код (n, k)=(6, 3); Найти спектр и производящую функцию кода. Решение: Количество разрешенных слов равно Nр=2k-1=23-1=7, к и n – количество строк и столбцов производящей матрицы. . , тогда |w| = . Ответ: производящая функция равна Т(z)=4z3+3z4, а, учитывая то, что кодовым расстоянием корректирующего кода называется минимальный вес разрешенных кодовых слов, кодовое расстояние данного кода d = min w = 3. Очевидно, что наилучшим как для исправления, так и для обнаружения ошибок будет являться код с наибольшим кодовым расстоянием. Для нахождения кодов с хорошими корректирующими свойствами используются границы. Так, например, для кодового расстояния двоичных кодов известны границы Хэмминга и Плоткина [2]: (1.16) Граница Хэмминга – определяет то минимальное значение длины проверочной части кодового слова (или наибольшее k), которое можно было бы получить, при условии, что данный код реализуем. Граница Плоткина – определяет оптимальное (наибольшее) значение кратности обнаруживаемых ошибок, которое можно достичь, при условии, что эквидистантный код с параметрами n и k реализуем. Эквидистантным кодом называется код, у которого расстояния между разрешенными кодовыми словами равны. Иначе: производящая функция содержит только одну составляющую, например: Т(z) = 4z3. Совершенный код – это код, обладающий максимальной исправляющей способностью. Параметры двоичного совершенного кода определяются как Графическая иллюстрация границы Хэмминга для двоичных кодов представлена на рисунке 1.6. Рисунок 1.6  Граница Хэмминга Граница Варшамова–Гильберта имеет вид: (1.17) где q – это основание кода, для двоичного кода q = 2. Смысл границы Варшамова–Гильберта: если , то существует блочный код с минимальным расстоянием d, имеющий, по меньшей мере, Nр кодовых слов. При этом количество слов Nр определяется выражением . (1.18) Интересной особенностью границы Варшамова–Гильберта является то, что для кодов Хэмминга эта граница дает точное значение числа разрешенных слов.Кодовое расстояние двоичных кодов по расчетам авторов можно определить из неравенства . (1.19) Искомое значение кодового расстояния находится путем постепенного увеличения параметра с одновременной проверкой неравенства. Максимальное значение параметра при котором данное неравенство выполняется и будет являться значением кодового расстояния кода. При этом знак равенства справедлив для кодов Хэмминга. При нахождении параметров двоичных совершенных кодов с исправлением ошибок кратности tи можно воспользоваться соотношением . (1.20) Код будет являться совершенным только тогда, когда для некоторых n и tи рассчитываемое r будет являться целым числом. Так, авторами найдены параметры (n,k) некоторых двоичных совершенных кодов для n<1000: • tи=1 (коды Хэмминга): (3,1,r=2), (7,4,r=3), (15,11,r=4), (31,26,r=5), (63,57,r=6), (127,120,r=7), (255,247,r=8), (511, 502,r=9); • tи =2: (5,1,r=4), (90,78,r=12); • tи =3: (7,1,r=6), (23,12,r=11) – код Голея; • tи =4: (9,1,r=8), (477,446,r=31); • tи =5: (11,1,r=10), (221,189,r=32), (441,404,r=37), (881,839,r=42). Аналогичным образом можно найти параметры других совершенных кодов. Соотношение … может быть распространено и на недвоичные коды, путем изменения основания логарифма. Выводы: • Для обеспечения максимальной скорости кода при обеспечении хороших корректирующих свойств необходимо использовать границу Хэмминга (верхняя граница по скорости кода). • В случае необходимости оценки числа разрешенных кодовых слов некоторого (n,k) кода необходимо использовать границу Варшамова–Гильберта. Для кодов Хэмминга граница Варшамова–Гильберта дает точное число кодовых слов. • При нахождении параметров совершенных кодов возможна комбинация границ Хэмминга и Варшамова–Гильберта. • Существует ограниченное число совершенных кодов с малым значением длины кодового слова n. 1.7 Вероятностные характеристики некоторых кодов 1.7.1 Код с четным числом единиц Данный код является двоичным блочным кодом и образуется путем добавления к кодовому слову k-символьного кода одного избыточного символа так, чтобы количество единиц в новом n-символьном слове было четным. В таблице 1.1 приведен пример кодирования кода k = 5, n = 6. Таблица 1.1 – Таблица кодирования k = 5 r = 1 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 Код обнаруживает все ошибки нечетной кратности. Обнаружение ошибок производится проверкой принятого кодового слова на четность, так как все разрешенные слова имеют четное число единиц, а неразрешенные - нечетное. Проверка на четность осуществляется суммированием всех символов слова по модулю двух. Если слово имеет четное число единиц, то сумма его символов по mod 2 равна 0. Если в канале связи ошибки независимы и вероятность искажения кодового символа равна , то согласно биномиальному закону распределения вероятность обнаружения ошибки равна (1.21). Вероятность искажения кодового слова равна вероятности того, что в кодовом слове на входе декодера произошла ошибка любой кратности от 1 до n . (1.22) Тогда вероятность необнаружения ошибки в кодовом слове равна (1.23) Скорость этого кода  0, 8. 1.7.2 Код с постоянным весом Примером кода с постоянным весом является семизначный код с отношением единиц и нулей в каждом кодовом слове, равным 3/4. Код имеет разрешенных кодовых слов, что является достаточным для помехоустойчивого кодирования всех кодовых слов 5-значного телеграфного кода. Семизначный код 3/4 относится к нелинейным неразделимым кодам с постоянным весом (см. раздел 1.7). В кодовом слове этого кода невозможно разделить символы на информационные и проверочные (избыточные). Обнаружение ошибок производится простым подсчетом единиц или нулей в принятом слове. Код обнаруживает все ошибки нечетной кратности и около 50% ошибок четной кратности. Ошибки не обнаруживаются, если в одном кодовом слове искажается одинаковое число единиц и нулей. Например, если в разрешенном слове 1011000 искажены первый и второй (или второй и третий и т.д.) кодовые символы, то кодовое слово превращается в другое разрешенное – 0111000 и т.д. Вероятность необнаруженной ошибки для кода 3/4 в канале связи с независимыми ошибками равна (1.24) Обнаруживающая способность семизначного кода выше, чем у шестизначного кода с проверкой на четность, но это достигается за счет увеличения избыточности. 1.7.3 Инверсный код Кодовые слова инверсного корректирующего кода образуются повторением исходного кодового слова (таблица 1.2). Если число единиц в исходном слове четное, оно повторяется в неизменном виде; если число единиц нечетное, то при повторении все символы исходного кодового слова инвертируются (нули заменяются единицами, а единицы - нулями). Таблица 1.2 – Таблица кодирования k r 1 2 3 4 5 6 7 8 9 10 a) a) б) б) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 а) в исходном кодовом слове четное число единиц, б) в исходном кодовом слове нечетное число единиц. Для обнаружения ошибок в кодовом слове, состоящем из символов производится две операции: 1) суммируются единицы, содержащиеся в первых k символах слова; 2) если число единиц четное, то r последующих символов сравниваются попарно с первыми k символами; если число единиц в первых символах нечетное, последующие символы перед сравниванием инвертируются. Несовпадение хотя бы одной из пар сравниваемых кодовых символов указывает на наличие ошибки в кодовом слове. Ошибка в кодовом слове не обнаруживается, если одновременно искажается четное число символов в исходном слове и соответствующие им кодовые символы в последовательности повторяемых символов. Например, если в кодовом слове 1011001001 искажены 1-й, 2-й, 6-й, 7-й символы, то ошибка не может быть обнаружена, так как образуется другое разрешенное слово – 0111010001. В канале связи с независимыми ошибками вероятность необнаруженной ошибки при использовании инверсного кода равна (1.25) т.е. существенно меньше, чем в аналогичных условиях для 6-значного кода с проверкой на четность и 7-значного кода с постоянным весом. Однако скорость инверсного кода еще меньше, чем 7-значного кода, и равна 0,5. 1.7.4 Блочный код (23,12) Код (23,12), известный как код Голея, имеет кодовое расстояние d=7 и может исправлять трехкратные ошибки и все ошибки меньшей кратности, поскольку tи ≤ (d-1)/2 = 3. Скорость кода R = k/n =12/23  0,52. Вероятность ошибки в кодовом слове на выходе декодера будет равна вероятности того, что в кодовом слове на входе декодера произошла ошибка , кратность которой t> tи . (1.26) Знак ( < ) относится к тем случаям, когда ошибки имели место только в проверочных символах, которые не подаются на выход декодера. Тогда вероятность ошибки декодирования символа на выходе декодера . (1.27) Так, например, если вероятность ошибки в канале p = 10 -4, то значение вероятности ошибки в кодовом слове на входе декодера кода (23, 12) будет равна, на выходе декодера - , а вероятность ошибки декодирования . Таким образом, даже для такого, относительно короткого кода, улучшение вероятностных характеристик канала является существенным. 1.8 Энергетический выигрыш от кодирования Энергетический выигрыш от кодирования (ЭВК) указывает на улучшение качества системы связи от использования данного способа кодирования или метода защиты от ошибок и определяется выражением (1.28) где h12, h22 – отношения сигнал/шум в сравниваемых системах связи при одинаковой вероятности ошибок на выходе; – относительная скорость системы с защитой от ошибок. Например, если первая система является системой без помехоустойчивого кодирования, а вторая система – с обнаружением ошибок и переспросом, то =(k/n)∙T/Tср; здесь Тср – средняя длительность передачи кодового слова (или символа длительности T) в системе с переспросом. Для системы c кодом, исправляющим ошибки без переспроса, относительная скорость равна =k/n=R, т.е. равна скорости кода. Если снять ограничения на длину кодового слова и полосу частот, то предельный выигрыш от помехоустойчивого кодирования при данной вероятности ошибки в канале связи с гауссовским шумом [6]: , (1.29) где E – энергия сигнала; N0 – спектральная плотность мощности помехи. Например, при когерентном приеме ортогональных сигналов и вероятности ошибки 10-5 предельное значение ЭВК достигает 14,2 дБ, при некогерентном приеме это значение еще выше. В реальных системах связи длина кода и занимаемая полоса частот ограничены, для этих условий может быть определен асимптотический выигрыш для данного кода, зависящий только от скорости кода и кодового расстояния. Для каналов с жестким решением на выходе демодулятора (1.30) Для декодеров с мягким решением на выходе демодулятора (1.31) Такой выигрыш будет достигаться, когда отношение сигнал/шум стремится к бесконечности (Е/N0 → ∞). Мягкие решения позволяют обеспечить дополнительный выигрыш от кодирования, но не более 3 дБ и существенно меньше при реальных отношениях сигнал/шум. В тех случаях, когда непрерывный канал, включая модулятор и демодулятор, заданы, выигрыш от помехоустойчивого кодирования можно оценить с помощью коэффициента исправления ошибок (повышения достоверности) , (1.32) где p и pд – вероятности ошибок на символ на входе и выходе декодера. Глава 2 ГРУППОВЫЕ КОДЫ 2.1 Групповые линейные коды Для построения кодов с хорошими характеристиками, обеспечивающие малую вероятность ошибки на выходе канала связи при заданной избыточности, требуется большой набор кодовых слов, и, следовательно, достаточно большое количество кодовых символов n в каждом из этих слов. Поэтому, возникает необходимость строить коды по определенным правилам, которые позволили бы осуществить операции кодирования и декодирования достаточно просто. Групповыми линейными кодами (n, k) называются коды, образующие конечную (абелеву) группу Gn над полем Галуа GF(2m) относительно линейной операции над элементами данного поля. Для двоичных кодов эта операция является сложением по модулю два (mod 2). Кодовые слова такого кода содержат n символов; причем к символов (как правило, начальных) – являются информационными, а остальные r=n-k – проверочными символами. Таким образом, любые кодовые слова данного кода можно записать как A=(), (k+r=n). При этом все множество разрешенных кодовых слов равно 2k и составляет подмножество группы Gn порядка 2n. Следовательно, количество запрещенных (неразрешенных) кодовых слов может быть найдено так: ; Так как разрешенные кодовые слова группового линейного кода образуют подгруппу относительно операции сложения по модулю два, то для определения всех кодовых слов подгруппы достаточно найти к линейно-независимых кодовых слов (сумма этих слов по mod 2 не должно равняться нулю). Остальные (2k-k-1)- кодовых слов находятся путем сложения по mod 2 этих k кодовых слов во всевозможных сочетаниях . Для построения группового кода удобно пользоваться понятиями: Производящая матрица и Проверочная матрица. Производящая матрица G кода (n, k) имеет n столбцов и k строк, в канонической форме образуется путем дополнения (r=n-k)- столбцов к единичной матрице размерности k  k. ==, (2.33) где к – количество столбцов в единичной подматрице, r – количество столбцов в символьной (дополнительной) подматрице, к – количество строк в матрице G. Символы {(b…b); (b…b); …; (bk1…bk1)} – могут быть найдены произвольно, однако должны выполняться условия: • вес каждой строки производящей матрицы wA≥ d; • dAA≥d, где dAA – расстояние между двумя кодовыми словами A и A, входящими в производящую матрицу; d – кодовое расстояние данного кода. При этом два кода, имеющие одинаковую размерность (n, k), но обладающие разными дополнениями (т.е. соответствующие элементы дополнений отличаются) – эквивалентны и будут иметь одинаковые спектры весов и корректирующую способность. Если же у двух кодов (n, k) – соответствующие n или k отличаются, то такие коды – не эквивалентны. Для определения алгоритмов кодирования и декодирования некоторого группового линейного кода строится проверочная матрица H. Проверочная матрица в каноническом виде записывается путем дополнения k столбцов к единичной матрице размерности (r x r) (дополнение приписывается слева от единичной матрицы). =. (2.34) Эта матрица используется для составления проверочных уравнений. Пример 2.17 Построить групповой двоичный код, исправляющий одиночные ошибки tи=1, длина кодового слова n=7. Решение задачи будем осуществлять поэтапно. 1 этап: Определение кодового расстояния d. Согласно (1.7) . Тогда , примем d=3. 2 этап: Определение количества проверочных элементов r производится согласно границе Хэмминга. , ; , , примем r =3. Скорость кода R=4/7. 3 этап: Строим производящую матрицу G: . Проверочные символы записываем так, чтобы расстояния между кодовыми словами A1, A2, A3 и А4 и веса этих слов были не меньше трех. Таким образом, = . 4 этап: Находим остальные(2k-k-1)=11 разрешенных кодовых слов: . Нулевое слово, хотя и не используется для передачи, также является разрешенным, так как оно определяется как сумма всех остальных разрешенных слов . Таким образом, мы определили все множество 2k=24=16 разрешенных кодовых слов, являющихся элементами поля GF(23). 5 этап: Проверка расстояний между разрешенными словами dAA d. Эта проверка, в принципе, эквивалентна определению веса каждого разрешенного слова полученного кода wi. Построим таблицу весов wi= (таблица 2.5). Таблица 2.3 – Таблица весов кода (7,4) Как видно из таблицы 2.5, кодовое расстояние построенного кода d=3. 6 этап: Определение спектра весов N(w) и производящей функции T(z) кода. Подсчет количества одинаковых весов дает: N(0)=1; N(3)=7; N(4)=7; N(7)=1. Таким образом, спектр весов имеет вид, показанный на рисунке 2.1. Рисунок 2.7 – Спектр весов кода (7,4) На этом рисунке также можно увидеть как определяется кратность гарантированно обнаруживаемых и исправляемых ошибок (tи=1 и tо=2, соответственно). Производящая функция будет иметь вид: T(z)=1·z0+7·z3+7·z4+1·z7. 7 этап: Формирование проверочной матрицы H. Для проверочной матрицы выбираем такие кодовые слова, проверочные символы которых образуют единичную матрицу, а число единиц четно . Таким образом, все строки проверочной матрицы будут удовлетворять проверкам на четность: Операция кодирования, т.е. вычисление проверочных кодовых символов, определяется системой уравнений: Таким образом, если на вход кодера поступает последовательность вида {0110}, то на его выходе кодовое слово: {0110b1b2b3}={0110011}. Для построения группового (n, k) кода с заданными параметрами n и tи, и определения правил кодирования и декодирования необходимо: 1) найти кодовое расстояние d; 2) найти количество проверочных элементов r; 3) построить производящую матрицу G; 4) построить проверочную матрицу H и систему проверочных уравнений. Синдромом ошибки называется вектор S(s1, s2, …, sr), который определяется выражением , (2.35) где HТ – транспонированная проверочная матрица кода. Кодовое слово без ошибок имеет нулевой синдром. Пример 2.18 Допустим, что в канале связи кодовое слово Аj было искажено. 1) Примем: Аj=А1={1000011}; Последовательность ошибок: e={0010000}→t=1. Тогда слово на входе декодера имеет вид: B1={1010011}. 2) Применяя к B1 проверочные соотношения, получим: где s1, s2 и s3 – элементы синдрома ошибки, указывающие на факт наличия ошибки в случае появления единицы при проверке. Однако эти элементы, сами по себе, не позволяют сделать вывод о том, какой из кодовых символов был искажен. 3) Устанавливаем, что искажен тот символ, который входит только в 1-ю и 3-ю проверки, как видно, это символ а3. 4) Для исправления ошибки символ а3 инвертируется с помощью исправляющей последовательности . Таким образом, на выходе декодера получается оценка декодируемого кодового слова в виде . На этом процесс декодирования заканчивается. Приведенную методику синдромного декодирования можно пояснить обобщенной схемой декодера группового линейного кода, рисунок 2.2. Рисунок 2.8 – Обобщенная структурная схема синдромного декодера группового линейного кода Если оценка последовательности ошибок точна (), то оценка декодируемого кодового слова является переданным кодовым словом (). Иначе представляет собой другое разрешенное кодовое слово. Вероятность последнего события называют вероятностью ошибки декодирования кодового слова . Эта вероятность может быть определена из следующего соотношения (2.36) где – вероятность правильного приема (отсутствие ошибок); – вероятность обнаружения или исправления ошибок (в системах с обнаружением или исправлением ошибок, соответственно); – вероятность неверного декодирования (ошибка декодирования). В системах с обнаружением ошибок значение меньше по сравнению с аналогичным значением для систем с исправлением ошибок. Однако следует учесть необходимость наличия обратной связи для исправления ошибок в первом случае, что во многом усложняет и удорожает систему связи в целом, а иногда использование обратной связи и вовсе является невозможным. Таким образом, для нахождения вероятности следует вычесть из полной вероятности (1) вероятность правильного приема и вероятность обнаружения/исправления ошибок (2.37) Вероятность правильного приема кодового слова длины n в каналах с независимыми ошибками вероятности p определяется как . (2.38) Режим обнаружения ошибок. Зная спектр весов кода можно определить . (2.39) Соответственно, значение вероятности ошибки декодирования . (2.40) Без знания спектра весов кода вероятность обнаружения ошибок можно определить только примерно (нижняя граница), как . (2.41) Тогда . (2.42) Режим исправления ошибок. Вероятность неверного декодирования в этом случае полностью определяется кратностью исправления ошибок кода и может быть рассчитана как , (2.43) или, с учетом больших значений n, . (2.44) Зачастую необходимо оценивать помехоустойчивость устройства защиты от ошибок по эквивалентной [4] вероятности ошибки бита, т.е. по вероятности ошибки декодирования кодового слова , приведенной к числу информационных битов . (2.45) Наиболее сложным элементом декодера (рисунок 2.2), определяющим возможность его реализации, является анализатор синдрома, так как синдромы ошибок используемых на практике корректирующих кодов могут содержать десятки и сотни элементов, что затрудняет реализацию устройств анализа системы проверочных уравнений. Так число логических операций, необходимых для декодирования кодового слова длиной n (сложность декодера), обычно, увеличивается экспоненциально с ростом n. Поэтому усилия разработчиков направлены, в основном, на поиск таких корректирующих кодов и методов декодирования, которые упрощали бы процедуру анализа синдрома ошибки. Существенное упрощение процедуры декодирования достигается при использовании кодов Рида–Маллера, Хэмминга и циклических кодов. Коды Рида–Маллера являются линейными кодами с простой процедурой декодирования, осуществляемой одним из методов голосования. Если это код первого порядка, то операция кодирования представляет собой просто повторение передачи кодового слова, а при декодировании применяется мажоритарный метод принятий решений о значении символов кодового слова. 2.2 Коды Хэмминга Кодом Хэмминга называется групповой (n,k) код, исправляющий одиночные ошибки и обнаруживающий двухкратные ошибки. Параметры n и k q-ичных кодов Хэмминга [3] определяются как . (2.46) где – число проверочных символов (r≥2). Проверочная матрица этого кода имеет r строк и n=2r-1 столбцов. Например, для кода Хэмминга (7,4), проверочная матрица имеет вид , (2.47) а его производящая матрица . (2.48) Коды Хэмминга могут быть модифицированы таким образом, что синдром ошибки, записанный в виде десятичного числа, укажет номер искаженного символа – за счет чего достигается существенное упрощение анализатора синдрома ошибок (рисунок 2.2). Рисунок 2.9 – Структурная схема декодера модифицированного кода Хэмминга Кодирование модифицированным кодом Хэмминга осуществляется путем добавления проверочных символов на позиции, определяемые как , (положительное целое число). Значение проверочных символов определяется путем проверки на четность разрядов, содержащих в своем двоичном номере единицу в позиции, соответствующей номеру позиции проверочного элемента. Например, для кода (7,4) при передаче некоторой информационной последовательности справедливо представление в виде рисунка 2.4, где символом «И» обозначены информационные элементы, «П» – проверочные элементы. Назначение бита И4 И3 И2 П3 И1 П2 П1 Десятичный номер бита 7 6 5 4 3 2 1 Двоичный номер бита 111 110 101 100 011 010 001 Рисунок 2.10 – Распределение символов кодовой посылки модифицированного кода Хэмминга (7,4) При этом проверочные биты находятся следующим образом: П1 = (И1 + И2 + И4) mod 2, (представлены все символы кодированной последовательности, позиции которых в двоичном виде соответствуют формуле XX1, где X – любое двоичное число); П2 = (И1 + И3 + И4) mod 2, (X1X); П3 = (И2 + И3 + И4) mod 2, (1XX). Пример 2.19 Закодировать модифицированным кодом Хэмминга (7,4), комбинацию из четырех информационных символов {И1,И2,И3,И4}={1,0,0,1}. Определяем значения проверочных символов. П1 = (И1 + И2 + И4) mod 2=(1+0+1) mod 2 = 2 mod 2 = 0, П2 = (И1 + И3 + И4) mod 2=(1+0+1) mod 2 = 2 mod 2 = 0, П3 = (И2 + И3 + И4) mod 2=(0+0+1) mod 2 = 1 mod 2 = 1. Таким образом, передаваемое кодовое слово кода Хэмминга имеет вид {И4,И3,И2,П3,И1,П2,П1}={1,0,0,1,1,0,0}. Допустим, что в канале связи был искажен бит И1. Кодовое слово приняло вид {И’4,И’3,И’2,П’3,И’1,П’2,П’1}={1,0,0,1,0,0,0}. Процесс декодирования осуществляется в приемнике согласно проверочным уравнениям: S1 = (П’1 + И’1 + И’2 + И’4) mod 2=(0+0+0+1) mod 2 = 1; S2 = (П’2 + И’1 + И’3 + И’4) mod 2=(0+0+0+1) mod 2 = 1; S3 = (П’3 + И’2 + И’3 + И’4) mod 2=(1+0+0+1) mod 2 = 0. Записываем результат проверки в виде S3S2S1=011, что равно десятичному числу 3, которое указывает номер искаженного разряда, начиная с младшего разряда. Следовательно, в этом разряде необходимо изменить 0 на 1. После исправления искаженного символа в информационных разрядах получим последовательность символов 1001, которая совпадает с переданной комбинацией информационных символов. Обнаруживающая способность кода Хэмминга может быть увеличена на единицу () введением дополнительной проверки на четность. В этом случае проверочная матрица расширенного кода Хэмминга (8,4), будет иметь вид , (2.49) а кодовое расстояние расширенного кода (8, 4) равно d=4. Однако следует отметить, что введение бита проверки на четность не сказывается на исправляющей способности внутреннего кода (7,4), . Для расширенного модифицированного кода Хэмминга кодовая последовательность имеет вид, представленный на рисунке 2.5. Побщ И4 И3 И2 П3 И1 П2 П1 8 7 6 5 4 3 2 1 Рисунок 2.11 – Распределение символов кодовой посылки кода (8,4) Где Побщ=(П1+П2+И1+П3+И2+И3+И4)mod2. Глава 3 ЦИКЛИЧЕСКИЕ КОДЫ 3.1 Циклические коды и их свойства Циклическим кодом называется линейный блочный код (n,k), который характеризуется свойством цикличности, то есть сдвиг влево на один шаг любого разрешенного кодового слова дает другое разрешенное кодовое слово, принадлежащее этому же коду; множество кодовых слов циклического кода представляется совокупностью полиномов степени (n-1) и менее, делящихся на некоторый полином g(x) степени r = n-k, который является сомножителем двучлена xn+1. Полином g(x) называется порождающим (или производящим). Циклические коды образуют циклическую группу, в которой кодовые слова образуются путем умножения некоторого кодового слова на x j Кодирование циклического кода осуществляется путем деления информационной последовательности на производящий полином. Поэтому для формирования циклического кода достаточно знать производящий полином g(x), который определяется как наименьшее общее кратное (НОК) минимальных функций mi(x), см. главу 2. g(x) =НОК{m1(x)∙…∙mr(x)}. (3.50) Одна из основных задач, стоящих перед разработчиками устройств защиты от ошибок (УЗО) при передаче дискретных сообщений по каналам связи, является выбор g(x) для построения циклического кода, обеспечивающего требуемое минимальное расстояние d для гарантийного обнаружения и исправления t-кратных ошибок. Существуют специальные таблицы по выбору g(x) в зависимости от предъявляемых требований к корректирующим свойствам кода [2]. Однако каждая разновидность циклических кодов имеет свои особенности формирования g(x). Поэтому при изучении конкретных циклических кодов будут рассматриваться соответствующие способы построения g(x). Длина кодового слова определяется как n=2m-1, (3.51) где m – расширение поля GF(2m). Число проверочных символов может быть найдено , (3.52) В свою очередь степень производящего полинома равна . Кодовое расстояние . Производящая матрица циклического кода определяется путем умножения степени () последовательно на . Проверочная матрица совершенного циклического кода определяется (3.53) где – строки проверочной матрицы (проверочные соотношения). К сожалению, для несовершенных циклических кодов упрощенного метода декодирования с построением проверочной матрицы не существует. Пример 3.1 Построить проверочную матрицу для циклического кода (15,11) и порождающего полинома g(x)=x4+x+1. Решение: Полином , полученный в результате деления () на g(x), и будет первой строкой проверочной матрицы. В двоичной записи этот полином выглядит как {000100110101111}, следовательно, проверочная матрица будет иметь вид Проверочная матрица позволяет вычислить синдром ошибки в виде полинома степени (n-k-1) (3.54) где B(x)  полином принятого кодового слова степени (n-1), е(x)  полином ошибок в канале степени (n-1). Для циклических кодов операция вычисление синдрома ошибки может быть записана в виде Помимо основных циклических кодов существует класс укороченных (усеченных) циклических кодов, которые образуются путем уменьшения числа информационных символов. Они имеют те же свойствами, что и основные коды: (n, k) – основной код, следовательно (n-1, k-1)…(n=r+1, k=1) – укороченные коды. Пример 3.2 Укороченные коды циклического кода (15,11) имеют вид: 3.2 Коды Боуза–Чоудхури–Хоквингема Лучшими кодами, обеспечивающими эффективную борьбу с независимыми ошибками, являются циклические коды Боуза–Чоудхури–Хоквингема (БЧХ). Эти коды являются обобщением кодов Хэмминга. Кодирование кодов БЧХ осуществляется с помощью регистра сдвига с ОС. В качестве примера на рисунке 3.1 приведена структурная схема кодера циклического кода (15,11), производящий полином кода g(x). Рисунок 3.12  Кодер циклического кода (15,11) Кодер представляет собой двоичный регистр сдвига с обратной связью через сумматоры по модулю 2 (mod 2), которые расположены в позициях, определяемых видом производящего полинома. Кодирование производится за 15 тактов. В течение первых 11 тактов ключ К1 замкнут, ключ К2 находится в положении 1; происходит вычисление проверочных символов в регистре сдвига путем деления поступающих на вход информационных символов на производящий полином, одновременно информационные символы через ключ К2 подаются на выход кодека. В течение последующих 4 тактов ключ К1 разомкнут, ключ К2 в положении 2; происходит считывание на выход кодера проверочных символов из ячеек регистра сдвига. Производящий полином кодов БЧХ определяется с помощью минимальных функций и кратности исправляемых ошибок g(x) =НОК{m1(x) … m2tи-1(x)}. (3.55) Некоторые производящие полиномы в виде неприводимых полиномов приведены из в таблице 3.1. Более подробные таблицы можно найти в специальной литературе, например, в Приложении А или в [6]. Широко распространены также методы отбора производящих полиномов с помощью ЭВМ. Таблица 3.4 – Простые неприводимые полиномы над GF(2) Степень Полином Степень Полином 2 x2 + x +1 16 x16+ x12+ x3+ x +1 3 x3 + x +1 17 x17+ x3+1 4 x4 + x +1 18 x18+ x7+1 5 x5 + x2 +1 19 x19+ x5+ x2+ x +1 6 x6 + x +1 20 x20 + x3 +1 7 x7 + x3 +1 21 x21 + x2 +1 8 x8 + x4 + x3 + x2 +1 22 x22 + x +1 9 x9 + x4 +1 23 x23 + x5 +1 10 x10 + x3+ 1 24 x24 + x7 + x2 + x +1 11 x11 + x2 +1 25 x25 + x3 +1 12 x12 + x6 + x4 + x +1 26 x26 + x6 + x2 + x +1 13 x13 + x4 + x3 + x +1 27 x27 + x5 + x2 + x +1 14 x14 + x10 + x6 + x +1 28 x28 + x3 +1 15 x15 + x +1 Пример 3.3 Построить код БЧХ при n =7 для исправления независимых ошибок кратности tи=1. Решение: 1) Для исправления независимых ошибок кратности tи=1 требуется кодовое расстояние . 2) Находим число расширение поля m: n =2m – 1; 7=2m; m=3. Следовательно, код строится над полем Галуа GF(2m)= GF(8). 3) Число проверочных символов ; . 4) Находим производящий полином, учитывая, что g(x)=, где i=1, 3, 5,,(2tи-1) – номера минимальных функций , определяются характером используемого поля Галуа GF(2m), см. пункт 2.1.5. Тогда i=d-2=3-2=1; g(x)=m1(x)=x3+x+1  1011 и проверочный полином . 5)Строим производящую матрицу, которая образуется добавлением n-k нулей к производящему полиному, записанному в виде двоичного числа; остальные строки матрицы представляют собой циклический сдвиг первой строки 6)Суммируя по модулю два во всевозможных сочетаниях строки производящей матрицы, получим остальные 11 разрешенных кодовых слов (из общего числа 2k-1=24-1=15, таблица 3.2. Нетрудно убедиться, что расстояние между любой парой кодовых слов в таблице 3.2 не меньше трех. Следовательно, полученный циклический код может исправлять любые одиночные ошибки. Таблица 3.5 – Кодовые слова циклического кода (7,4) № Кодовые слова № Кодовые слова № Кодовые слова п/п k r п/п k r п/п k r 1 2 3 4 5 0001 0010 0101 1011 0011 011 110 100 000 101 6 7 8 9 10 0100 1010 0111 1001 1110 011 100 111 011 010 11 12 13 14 15 1000 0110 1111 1100 1101 101 001 111 010 001 3.3 Декодирование циклических кодов При декодировании кодового слова циклического кода также производится его деление на производящий полином. Неискаженное кодовое слово должно делиться на производящий полином без остатка. Наличие остатка (синдрома ошибки) указывает на искажение слова. Для определения искаженного символа кода и его исправления необходимо с полученным остатком произвести ряд операций. Иногда исправляются только одиночные ошибки, так как с увеличением кратности исправляемых ошибок резко усложняется реализация декодирующего устройства. Операции деления кодовых слов на производящий полином в процессе кодирования и декодирования производятся с помощью регистров сдвига с обратными связями. Обратные связи располагаются в соответствии с заданным производящим полиномом и осуществляются через сумматоры по mod 2. Как уже отмечалось, коды БЧХ используются в каналах с независимыми ошибками. Эти же коды способны обнаруживать пакеты ошибок, если их длина не превышает числа проверочных символов кода. Под пакетом ошибок обычно понимается группа кодовых символов, вероятность ошибки внутри которой существенно выше средней вероятности ошибок в последовательности, причем первый и последний символы пакета содержат ошибку. Однако для обнаружения и исправления пакетов ошибок лучше использовать специальные коды, которые наиболее эффективны в каналах связи с группирующимися (коррелированными) ошибками. К числу таких кодов относятся циклические коды Файра. Длина пакета обнаруживаемых таким кодом ошибок значительно превышает число проверочных символов кодового слова. Можно также использовать коды БЧХ с перемежением символов канала. Эффективность циклических кодов, как правило, увеличивается с увеличением длины кодовых слов. Поэтому в современной практике иногда применяются циклические коды, длина кодовых слов которых . При кодировании и декодировании циклических кодов используется тот факт, что любое кодовое слово данного кода делится без остатка на производящий полином. Поэтому при кодировании к последовательности информационных символов добавляется справа r нулей и получившаяся последовательность элементов делится на производящий полином. Остаток от деления представляет собой последовательность проверочных символов, которая передается в канал связи после передачи информационных символов. Пример 3.4 Последовательность информационных символов имеет вид 0110. Найти проверочные символы при кодировании кодом (7,4) из примера 3.3. Решение: k r g(x) 0110.000 1011 101.1 0111 11.10 10.11 1.010 1.011 .001 - остаток В результате образуется и передается кодовое слово 0110001 (кодовое слово №12 из таблицы 3.2) При декодировании кодового слова циклического кода также производится его деление на производящий полином. Неискаженное слово должно делиться на производящий полином без остатка. Остаток указывает на искажение декодируемого слова и является синдромом ошибки (3.5). Пример 3.5 Найти синдром ошибки декодируемого кодового слова кода (7,4) из примера 3.3 Решение: а) принятое кодовое слово без ошибок 0110.001 | 1011 101.1 | 0111 11.10 10.11 1.011 1.011 .000  остаток: Si(x)=0 б) принятое кодовое слово с ошибками 0111.001 | 1011 101.1 | 011 10.10 10.11 .011  остаток: Si(x)0 Для определения искаженного символа кода и его исправления необходимо с полученным остатком (синдромом ошибки) произвести еще ряд операций, которые будут рассмотрены ниже. К оптимальным методам декодирования циклических кодов, в том смысле, что они минимизируют среднюю вероятность ошибки (3.56) относятся методы декодирования по максимуму апостериорной вероятности (МАВ), а при одинаковых априорных вероятностях p(Ai) по максимуму правдоподобия (МП). Причем декодирование по максимуму правдоподобия иногда предпочтительнее, поскольку обеспечивает минимум потерь информации. Трудности реализации оптимальных методов декодирования связаны с тем, что декодер должен иметь большую память, равную (или близкую по объему) числу кодовых слов используемого кода. Поэтому оптимальные методы, как правило, используются для исправления ошибок малой кратности (одиночных ошибок или одиночных пакетов ошибок): это метод, основанный на выборе синдрома и метод стандартной расстановки. Сущность метода, основанного на выборе синдрома: 1 До декодирования вычисляются все синдромы ошибок Si(x), исправляемых данным кодом, и сводятся в таблицу вместе с конфигурациями соответствующих ошибок ei(x), i=1 … 2n-k. 2 Вычисляется синдром ошибки Sj(x) декодируемого кодового слова. 3 Пошаговым сравнением синдрома Sj(x) с синдромами Si(x), хранящимися в таблице, находится конфигурация ошибки ej(x), соответствующая Sj(x). 4 Производится исправление ошибки в принятом кодовом слове суммированием (по модулю 2) этого слова с последовательностью ошибок ej(x). Сложность этой процедуры связана с размерами таблицы, состоящей из 2n-k строк длины n. Структурная схема такого декодера показана на рисунке 3.2. Рисунок 3.13 – Декодер с табличным поиском синдрома Используя свойства циклических кодов и метод стандартной расстановки, можно уменьшить объем таблицы и ускорить сравнение. В других случаях, как, например, это реализовано в структурной схеме рисунок 3.3, хранятся синдромы только однократных ошибок, а синдромы двух- и трехкратных ошибок вычисляются (кратность исправления ошибок в приведенном примере равна трем). Рисунок 3.14 – Структурная схема синдромно-матричного декодера В качестве примера на рисунках 3.4 и 3.5 приведены структурные схемы кодера и декодера циклического кода (15,5), имеющего кодовое расстояние d=7 и исправляющего любые конфигурации ошибок кратности 3. Производящий полином кода g(x) показан на рисунках. Кодер представляет собой двоичный регистр сдвига с обратной связью через сумматоры по модулю 2, которые расположены в позициях, определяемых видом производящего полинома. Кодирование производится за 15 тактов. В течение первых 5 тактов ключ К1 замкнут, ключ К2 находится в положении 1; происходит вычисление проверочных символов в регистре сдвига путем деления поступающих на вход информационных символов на производящий полином, одновременно информационные символы через ключ К2 подаются на выход кодека. В течение последующих 10 тактов ключ К1 разомкнут, ключ К2 в положении 2; происходит считывание на выход кодера проверочных символов из ячеек регистра сдвига. Рисунок 3.15  Кодер циклического кода (15,5) Декодер рассматриваемого кода (рисунок 3.5) построен по синдромно-матричной схеме. Рисунок 3.16  Синдромно-матричный декодер циклического кода (15,5) При включении декодера проиводится вычисление матрицы синдромов одиночных ошибок (3.8), таких синдромов у данного кода 15 (при необходимости экономии объема памяти для хранения синдромов кодов большой длины могут вычисляться и храниться только синдромы ошибок в информационных символах S1(x)Sk(x), поскольку вид синдромов ошибок в проверочных символах Sk+1(x) Sn(x) очевиден и одинаков для всех кодов). (3.57) Дополнительно в декодере хранится нулевой синдром S0(x)=0000000000, указывающий на отсутствие ошибок. Затем принятое кодовое слово поступает в буферный регистр (для хранения на время декодирования) и в регистр синдрома для вычисления синдрома ошибки этого слова S(x) (как и в кодере в регистре синдрома производится деление принятого кодового слова на производящий полином, элементы синдрома S(x): S0, S1, S2, S3, S4, S5, S6, S7, S8, S9 представляют собой остаток от деления). В схеме сравнения 1 синдромы S0(x) Sn(x) сравниваются с синдромом ошибки декодируемого кодового слова. Если S(x) = S0(x), то ошибок нет, на выходе схемы сравнения 1 сигнал “да” и декодирование сводится к считыванию информационных символов из буферного регистра на выход декодера. Если S(x)  S0(x), то начинается операция поиска конфигурации одиночной ошибки; для этого синдромы одиночных ошибок поочередно подаются на схему сравнения 1. При обнаружении равенства S(x) = Si(x), i= 1 … 15 на выходе схемы сравнения 1 появляется сигнал «да», по которому в блоке формирования ошибок декодера формируется последовательность ошибок с символом 1 в позиции i. Если S(x)  Si(x), то начинается операция поиска конфигурации двойной ошибки; для этого в блоке вычисления синдромов двойных ошибок производится попарное сложение элементов строк матрицы синдромов (2.14) и сравнение суммы Sij(x) с синдромом S(x) в схеме сравнения 2. При обнаружении равенства S(x) = Sij(x), i= 1 … n, j= 1 …(n-1) на выходе схемы сравнения 2 появляется сигнал «да», по которому формируется последовательность ошибок с символами 1 в позициях i и j. Если S(x)  Sij(x), то начинается операция поиска конфигурации тройной ошибки; для этого в блоке вычисления синдромов тройных ошибок производится поочередное сложение элементов трех строк матрицы синдромов (2.20) и сравнение суммы Sijk(x) с синдромом S(x) в схеме сравнения 3 до обнаружения равенства S(x) = Sijk(x), i= 1 … n, j= 1 …(n-1), k= 1 …(n-2). В сумматоре по модулю 2 на выходе буферного регистра происходит сложение символов декодируемого кодового слова и символов последовательности ошибок eijk(x) и на выход декодера подается декодированная последовательность информационных символов. Как известно, существенным недостатком синдромно-матричного декодера является малое быстродействие при исправлении ошибок большой кратности из-за быстрого увеличения числа синдромов с ростом кратности исправляемых ошибок. В рассматриваемом примере код имеет n=15 синдромов одиночных ошибок, n(n-1)=1514=210 синдромов двойных ошибок и n(n-1)(n-2)=151413=2730 синдромов тройных ошибок. Для более длинных кодов число возможных синдромов ошибок может быть необозримо велико. При необходимости кратность исправляемых данным кодом ошибок может быть ограничена. Для этого сокращается число установленных в схеме декодера блоков вычисления синдромов, а по сигналу перехода управления к этому блоку формируется сигнал «отказ от декодирования», по которому декодирование прекращается, а по дополнительному выходу сообщается об обнаружении ошибки неисправляемой кратности. Другим методом упрощения синдромно-матричного декодера является декодер Меггита, представляющий собой синдромный декодер, исправляющий одиночные ошибки. В нем хранится только один синдром ошибки: S15(x)=x3+1 (соответствует конфигурации ошибки e15(x)=x14). Синдромы остальных одиночных ошибок циклически сдвигаются в регистре синдрома до совпадения с S15(x); число циклов сдвига плюс единица равно номеру искаженного кодового символа. Поэтому такие декодеры иногда называются декодерами с вылавливанием ошибок. Структурная схема декодера показана на рисунке 3.6. Рисунок 3.17 – Декодер Меггита для циклического кода (15,11) Декодер работает следующим образом. Кодовое слово (с ошибками или без них) в виде последовательности из 15 двоичных символов поступает в буферный регистр и одновременно в регистр синдрома, где производится деление этого слова на производящий полином кода g(x)=x4+x+1 в результате чего вычисляется синдром ошибки Sj(x): S0j, S1j, S2j, S3j  элементы синдрома. Ошибка обнаруживается, если хотя бы один элемент синдрома не равен нулю. Исправление ошибок производится в следующих 15 циклах сдвига. В каждом i-ом цикле проверяется равенство Sj+i(x)=S15(x) и в благоприятном случае на выходе схемы “И” появляется импульс коррекции ошибки, инвертирующий символ на выходе буферного регистра. В пунктирном квадрате (рисунок 3.6) показана возможная модификация регистра синдрома, упрощающая реализацию схемы И. Для этого принимаемая последовательность до ввода в регистр синдрома умножается на x4, тогда синдром ошибки в первом символе кодового слова будет равен S15(x)= x3. Однако эти методы декодирования уже не являются оптимальными, так как исправление ошибок производится в пределах заданной или гарантируемой кодом кратности tи  (d-1)/2. (3.58) Для исправления ошибок большой кратности, как правило, используются методы субоптимального декодирования, которые позволяют упростить процедуру декодирования при незначительном снижении качества. К субоптимальным методам декодирования, кроме рассмотренных выше синдромно-матричных декодеров, относятся перестановочные методы, алгебраические методы (мажоритарный, пороговый и пр.) и некоторые другие. Эти методы отличаются тем, что исправление ошибок производится, как правило, в пределах гарантируемой кодом кратности (3.9). 3.4 Субоптимальные методы декодирования циклических кодов 3.4.1 Перестановочные методы Перестановочные методы декодирования основываются на свойстве симметрии линейных кодов, т. е. на существовании такого множества перестановок элементов кодовой последовательности, которые переводят ее в последовательность, принадлежащую тому же коду. Перестановки в кодовой последовательности, можно найти такую перестановку , в результате которой на информационных позициях будут находиться только неискаженные элементы. По известной процедуре кодирования, обозначим ее через, определяются проверочные элементы последовательности и тем самым исправляются искаженные элементы. Используя обратную перестановку получим исправленную кодовую последовательность. Перестановку, в результате которой произошло правильное исправление, можно определить из неравенства (3.59) где - последовательность, получившаяся в результате перестановки - исправленный вариант последовательности . Алгоритм декодирования (алгоритм Прэнжа) [15] формулируется следующим образом: для перестановки найти ; если для и неравенство (3.5) выполнилось, считать декодированным вариантом принятой последовательности последовательность ; если неравенство (3.5) не выполнилось, перейти к перестановке. Наибольшее распространение получила модификация алгоритма Прэнжа, предложенная Кассами и Рудольфом [15]. Сущность этого метода заключается в том, что часть искаженных элементов в результате циклической перестановки попадает на проверочные позиции, а искаженные элементы, оставшиеся на информационных позициях, исправляются с помощью покрывающих последовательностей. Последовательность элементов покрывает подмножество ошибок, если для любой последовательности е из этого подмножества можно найти такой ее циклический сдвиг , что т. е. на информационных позициях сдвинутая последовательность ошибок совпадает с покрывающей комбинацией. С помощью одной покрывающей комбинации можно исправить лишь часть ошибок. Для исправления всего множества ошибок нужно использовать несколько покрывающих комбинаций, причем с ростом длины растет и количество покрывающих комбинаций. Момент совпадения с можно определить по выполнению неравенства (3.60) где - вес последовательности f(x); - синдром j-й покрывающей комбинации; - синдром принимаемой последовательности. Для декодирования по методу Кассами–Рудольфа надо производить циклические сдвиги принимаемой последовательности, вычислить вес для каждой покрывающей комбинации. Если неравенство (3.6) выполнилось после i-го сдвига j-й покрывающей последовательности, считать декодированным вариантом принятой последовательности последовательность Структурная схема декодера Кассами–Рудольфа для кода Голея (23,12) приведена на рисунке 3.7. Производящий полином этого кода g(x)=x11+x9+x7+x6+x5+x+1; множество ошибок, кратность которых не превышает трех, покрывается тремя последовательностями ошибок e1(x)=0, e17(x)=x16, e18(x)=x17, имеющих синдромы S1(x)=0, S17(x)=x8+x7+x4+x3+x+1, S18(x)=x9+x8+x5+x4+x2+x. Декодер отслеживает синдром ошибок декодируемого кодового слова, отличающийся от S1(x) не более чем в трех позициях, а также синдромы ошибок, отличающиеся от S17(x) и S18(x) не более чем в двух позициях. Рисунок 3.18  Декодер Кассами - Рудольфа циклического кода (23,12) Декодирование производится в течение двух циклов. В первом цикле в течение 23 тактов производится запись принятого кодового слова в буферный регистр (п1=0) и вычисление синдрома ошибки в синдромном регистре (п2=0). Во втором цикле (п1=1) из 23 тактов производится поиск и исправление ошибок путем циклического сдвига синдрома ошибки и его сравнения с покрывающими синдромами в анализаторе синдрома. Одновременно циклически сдвигается кодовое слово в буферном регистре. Позиции ошибок обнаруживаются при удовлетворении какого-либо из неравенств в анализаторе синдрома; на выходе соответствующей схемы анализатора появляется сигнал, по которому выход синдромного регистра подключается (п2=1) к сумматору в цепи циклического сдвига буферного регистра для исправления ошибок. Если ошибка обнаруживается второй или третьей схемами анализатора, то дополнительно исправляются ошибки в 17-й или 18-й ячейках буферного регистра в соответствии с номером покрывающего синдрома; одновременно производится стирание этого синдрома в синдромном регистре. После 23-го цикла производится проверка состояния синдромного регистра и, если остаток не превышает двух единиц, его содержимое используется для коррекции состояний первых 11 ячеек буферного регистра. На этом декодирование заканчивается и на выход выдаются информационные символы, расположенные в первых 11 ячейках буферного регистра; одновременно на вход может подаваться новое кодовое слово (п1=0). 3.4.2 Мажоритарное и пороговое декодирование К числу методов, использующих для декодирования алгебраические особенности линейных кодов, относится мажоритарный метод декодирования циклических кодов. Этот метод основан на возможности составления системы ортогональных (разделенных) проверок для каждого символа принятого сообщения. Каждая i-я строка проверочной матрицы H задает одно соотношение, связывающее между собой символы кодового слова (a0, a1, a2, a3, …, an) hi0 a0+hi1 a1 +…+ hi n-\ an-1 =0, i=1, 2,3, …, n – k. Набор этих соотношений называется контрольными проверками, на основе которых формируется система ортогональных (разделенных) проверок, удовлетворяющих следующим требованиям: • число проверочных соотношений должно быть ≥2tи; • проверяемый символ ai входит в каждую контрольную проверку; • любой другой символ aj (ji) входит лишь в одну из проверок. При выполнении этих условий ошибка в проверяемом символе ai искажает все проверки, а ошибка в символе aj (ji) искажает только одну проверку, что позволяет принимать решение о значении символа ai по большинству проверок. На рисунке 3.8 приведена структурная схема мажоритарного декодера для циклического кода (7,3). Код задается производящим полиномом g(x)=x4+x3+x2+1, а его проверочная матрица H и система разделенных проверок имеют вид Второе проверочное соотношение образовано суммированием по модулю два второй и третьей строк проверочной матрицы. Дополняя систему уравнений соотношением a1=a1, получаем разделенные проверки для символа a1 в виде Декодирующее устройство состоит из буферного регистра и мажоритарного элемента (М). Принятое кодовое слово записывается в буферный регистр. Решение о значении принятого символа принимается по большинству проверок, исправленный первый символ считывается с выхода мажоритарного элемента, поступает на выход декодера и через ключ в седьмую ячейку регистра. В результате циклических сдвигов принятого кодового слова в буферном регистре исправляются остальные символы кодового слова. Таким образом, декодирование происходит в течение 14 тактов: первые 7 тактов ввод принятого кодового слова в буферный регистр (ключ в нижнем положении), следующие 7 тактов обнаруживаются и исправляются ошибки в символах принятого слова. Рисунок 3.19 – Мажоритарный декодер циклического кода (7,3) Мажоритарный метод декодирования может быть реализован также в виде порогового декодера, показанного на рисунке 3.9. Пороговый декодер является синдромным декодером, у которого анализатор синдрома определяет значение символа ошибки (0 или 1) в декодируемом кодовом символе мажоритарным методом (по большинству элементов синдрома Si). Элементы синдрома ошибки (S0, S1, S2, S3) определяются в регистре синдрома путем деления принятого кодового слова на производящий полином (ключ К замкнут). В течение следующих семи тактов ведется поиск и исправление ошибки (ключ К разомкнут). Сложение по модулю 2 первого и третьего элементов синдрома обеспечивает ортогональность проверок. Рисунок 3.20  Пороговый декодер циклического кода (7,3) В пороговом элементе сумма элементов синдрома на каждом такте сдвига регистра синдрома и буферного регистра сравнивается с порогом, который для данного кода равен 2. Пороговый элемент выдает на выходе символ 1, когда сумма элементов синдрома 2; при этом очередной символ, поступающий с выхода буферного регистра, инвертируется в сумматоре по модулю 2 (происходит исправление обнаруженной ошибки). Мажоритарный метод является наиболее быстрым и простым из известных методов декодирования. Однако он применим лишь для сравнительно небольшой группы линейных кодов (кодов Рида–Маллера и некоторых других циклических и сверточных кодов [3]). Глава 4 АЛГЕБРАИЧЕСКОЕ ДЕКОДИРОВАНИЕ КОДОВ БЧХ 4.1 Недвоичные циклические коды БЧХ 4.1.1 Коды Рида-Соломона Построение недвоичных (q-ичных) кодов БЧХ мало отличается от построения двоичных кодов и сводится к определению производящего полинома g(x), который либо неприводим, либо представляет собой произведение неприводимых (примитивных) полиномов. Важным и широко используемым подклассом (подмножеством) циклических кодов БЧХ являются коды Рида-Соломона (коды РС). Для этих кодов компоненты кодовых слов и их преобразования могут находиться как в двоичном поле, так и в q-ичном поле GF(q >2). В дальнейшем будем рассматривать только коды РС над двоичным полем GF(q) = GF(2m). Производящий полином кода РС определяется просто g(x)=(x-)( x-2)( x-3) … (x-2t), (4.61) где  - примитивный элемент поля GF(2m), а длина m-ичного кодового слова равна n = 2m– 1. Пример 4.3 Для кода РС (7,3) с tи =2 над GF(8) производящий полином имеет вид g(x)=x4+(z+1)x3+x2+zx+(z+1), где элементы поля записаны в виде полиномов z. Элементы поля GF(8): 0= 1 (001); 1= z (010); 2= z2 (100); 3= z+1 (011); 4= z2+z (110); 5= z2+z+1(111); 6= z2+1 (101); 7= 0=1 (001). Поэтому порождающий полином можно записать в виде g(x) = x4 + 3x3 + x2 + x + 3. Таблица производящих полиномов некоторых кодов РС приведена в Приложении А. Как видно из (4.18) и примера 4.3 производящие полиномы кодов РС g(x) содержат все степени x, начиная от нуля до 2tи. Поэтому в Приложении А для производящих полиномов кодов РС указаны, начиная с младшего разряда g(x), только степени i элементов поля i, которые в данном случае являются коэффициентами соответствующих разрядов полинома. Коды РС применяются для исправления ошибок и стираний в каналах с пакетирующимися ошибками и в качестве внешнего кода при каскадном кодировании в аппаратуре радиорелейной, сотовой и космической связи с учетом того, что после декодирования внутреннего кода ошибки группируются. Важной его особенностью является то, что этот код имеет кодовое расстояние d = (n-k +1) = r +1 (4.62) и является кодом с максимальным кодовым расстоянием. Поэтому коды РС всегда оказываются короче всех других циклических кодов над тем же алфавитом и являются оптимальными с точки зрения эффективности использования избыточности, так как максимальная кратность исправляемых ошибок t равна половине проверочных символов в m-ичном кодовом слове. Кодирование кода РС производится так же, как и любых циклических кодов: проверочные символы образуются как остаток от деления m-ичной информационной последовательности на производящий полином. Это может быть сделано с помощью m-ичного регистра сдвига, который может быть реализован на m двоичных регистрах с обратными связями, определяемыми коэффициентами производящего полинома, либо программно на ЭВМ. В общем случае декодирование кодов РС является существенно более сложной процедурой, чем двоичных циклических кодов, так как необходимо определить не только позиции ошибок, но и их величину. Декодирование с применением алгоритма Берликэмпа–Месси можно реализовать как во временном (рисунок 4.4), так и в частотном пространствах (рисунок 4.2). Временной декодер недвоичных кодов не содержит преобразования Фурье, упрощенный алгоритм его работы показан на рисунке 4.7. Для декодирования кодового слова B(x) необходимо знать длину кодового слова n, кратность исправляемых ошибок t и все элементы поля (блок 2), в котором определен данный код. В декодере реализуется алгоритм Берликэмпа–Месси во временном пространстве (блок 3), в котором с помощью рекурсивной процедуры в течение 2t циклов формируется регистр, генерирующий полином локатора ошибок. Затем в течение (n-2t) циклов определяются значения ошибок (блок 4). Декодированное кодовое слово получается сложением в соответствующих позициях принятого слова и последовательности значений ошибок. Рисунок 4.21  Алгоритм декодирования кода РС Процесс формирования уравнений локатора ошибок и значений ошибок в частотном пространстве показан в примере 4.4. Пример 4.4 Декодирование кода РС (15,9), исправляющего t≤3 ошибок над полем GF(24). Кодовые слова состоят из n = 24-1=15 четверичных символов, соответственно в двоичных символах это код (60,36). Производящий полином кода g(x)=(x+α)(x+α2)(x+α3)(x+α4)(x+α5)(x+α6)=x6+α10x5+α14x4+α4x3+α6x2+α9x+α6. Решение: для упрощения решения задачи примем, что полином информационных символов имеет вид: U(x)=0(передаются все нули). Тогда кодовое слово на входе декодера будет иметь вид B(x)=αx7+α5x5+α11x2=e(x), то есть совпадает с полиномом ошибки. Вычисляем компоненты синдрома ошибки в частотном пространстве, которые определяются путем подстановки корней g(x) в кодовое слово B(x). Всего имеется 6 компонентов синдрома, так как 2t=2*3=6: S 1=αα7+α5α5+α11α2 =α12, S 2=αα14+α5α10+α11α4 =1, S 3=αα21+α5α15+α11α6 =α14, S 4=αα28+α5α20+α11α8 =α13, S 5= αα35+ α5α25+ α11α10 =1, S 6= αα42+ α5α30+ α11α12 =α11. Процесс формирования уравнения локатора ошибок и уравнения значений ошибок с помощью алгоритма Берликэмпа–Месси показан в таблице 4.2. Таблица 4.6 – Формирование уравнений локатора ошибок и значений ошибок r Δr T(x) P(x) Λ(x) (x) L 1 1 1 1 α12(15) 1+α12x α3 1+α12x α12x 1 2 α7(11) 1+α3x α3x 1+α3x α12x 1 3 1 1+α3x+α3x2 α3x+1 1+α3x+α3x2 α12x 2 4 1 1+α14x α3x2+x 1+α14x α12x+α12x2 2 5 α11(14) 1+α14x+α11x2+α14x3 α3x+α4 1+α14x+α11x2+α14x3 α12x+α12x2+α8x3 3 6 1+α14x+α11x2+α14x3 α3x2+α4x 1+α14x+α11x2+α14x3 α12x+α12x2+α8x3 3 Уравнение локатора ошибок имеет вид Λ(x)= 1+ α14x+ α11x2+ α14x3. Корни этого уравнения указывают позиции ошибок. Можно записать Λ(x)=(1+α7x)(1+ α5x)(1+ α2x), следовательно, ошибки в 7, 5 и 2 разрядах принятого слова. Уравнение значений ошибок имеет вид (x)= α12x+ α12x2+ α8x3. Корни этого уравнения показывают значения ошибок. Можно показать, что корнями этого уравнения являются α, α5, α11, что соответствует значениям ошибок в 7, 5 и 2 разрядах декодируемого кодового слова B(x). Скорость работы кодека во временном пространстве теоретически убывает обратно пропорционально n2, практически получаются несколько другие соотношения из-за различной избыточности кодов и преобразования m-ичных слов в двоичные. Однако скорость декодирования рассматриваемого декодера мало зависит от кратности исправляемых ошибок, что является его хорошим свойством в отличие от других алгоритмов декодирования циклических кодов. Как отмечалось в разделе 4.4 декодирование недвоичных кодов, а значит и кодов РС, при значительной длине кодового слова n происходит быстрее в частотном пространстве (см. рисунок 4.2). Оценка вероятности ошибок декодирования кодов РС в каналах с независимыми ошибками может быть определена по формуле (4.63) Коэффициент 0,5 перед суммой учитывает среднее число искаженных двоичных символов в m-ичных символе декодируемого слова кода РС. 4.1.2 Декодер кода РС с вылавливанием ошибок Декодер кода РС с вылавливанием ошибок является модификацией декодера Меггита. Рассмотрим декодер с вылавливанием ошибок для (7,3) кода Рида–Соломона, исправляющий одиночные и двойные ошибки над полем GF(8), рисунок 4.8. Рисунок 4.22  Декодер кода РС (7,3) с вылавливанием ошибок Предположим, что произошедшие ошибки расположены близко друг от друга. Определим длину конфигурации ошибок как наименьшее число последовательных разрядов регистра, которые надо просмотреть для того, чтобы при некотором циклическом сдвиге конфигурации ошибок все ошибочные позиции оказались внутри этих разрядов. Предполагается, что наибольшая длина исправляемой конфигурации не превосходит длины синдрома. Тогда при некотором циклическом сдвиге синдром принимает вид, совпадающий с конфигурацией исправляемых ошибок, т.е. для таких кодов синдром можно циклически сдвигать до тех пор, пока не получится исправляемая конфигурация (таблица 4.3). Для завершения исправления ошибок надо теперь вычесть содержимое синдрома из соответствующего циклического сдвига принятого вектора. Для декодирования необходим 21 такт (7 тактов регистра для вычисления синдрома ошибки, 7 тактов для вылавливания первой ошибки и 7 тактов для вылавливания второй ошибки). Возврат выходных символов в буферный регистр используется для исправления второй ошибки. В двоичной реализации восьмеричные разряды регистра сдвига представляют собой параллельные регистры с тремя двоичными разрядами. Все линии передачи данных в каждый момент времени передают три двоичных символа. Элементы умножения на x+1 (на 3) и на x (на ) в цепи обратной связи являются просто определенными устройствами двоичной логики с тремя входами и тремя выходами. Прочие производимые операции не отличаются от аналогичных операций, производимых в двоичном поле. Элементы синдрома ошибки также являются трехразрядными числами и определяются путем деления принятого кодового слова на производящий полином, анализатор синдрома ошибки представляет собой простую логическую схему. Из-за большого разнообразия применяемых кодов создание специализированных кодеров и декодеров не всегда экономически оправдано. Это делает актуальной разработку программных методов кодирования и декодирования. В таблице 4.3 приведены результаты вылавливания ошибок для схемы декодера кода РС (7,3). Переданное кодовое слово: A(x)=α4x6+α4x4+α3x3+ α6x+α6; Полином ошибок e(x)=α4x4+α3 (2 ошибки); Декодируемое слово: B(x)=α4x6+α3x3+α6x+α4. Таблица 4.7 – Таблица вылавливания ошибок Такт Синдромный регистр Буферный регистр 0 0 0 0 0 0 0 0 0 0 0 1 1 α5 α4 1 α4 0 0 0 0 0 0 2 α3 α3 α4 α6 0 α4 0 0 0 0 0 3 α2 α α4 α 0 0 α4 0 0 0 0 4 α3 α4 α3 α6 α3 0 0 α4 0 0 0 5 α2 α α3 α5 0 α3 0 0 α4 0 0 6 α4 0 0 α6 α6 0 α3 0 0 α4 0 7 α 6 0 α 3 α 6 (синдром) α4 α6 0 α3 0 0 α4 8 α2 α2 α6 α5 α4 α4 α6 0 α3 0 0 9 α 1 α3 α5 0 α4 α4 α6 0 α3 0 10 α α5 α4 1 0 0 α4 α4 α6 0 α3 11 α3 0 α4 α6 α3 0 0 α4 α4 α6 0 12 α2 α α6 α 0 α3 0 0 α4 α4 α6 13 α 4 0 0 α 3 (выловленная ошибка) α6 0 α3 0 0 α4 α4 14 0 α4 0 0 α6 α6 0 α3 0 0 α4 15 0 0 α4 0 α6 α6 0 α3 0 0 | α4  символы на выходе 16 0 0 0 α 4 (выловленная ошибка) α 6 α 6 0 α 3 0 | 0 α4 17 0 0 0 0 α6 α6 0 α3| α4 0 α4 18 0 0 0 0 α6 α6 0| α3 α4 0 α4 19 0 0 0 0 α6 α6| 0 α3 α4 0 α4 20 0 0 0 0 α6 | α6 0 α3 α4 0 α4 21 0 0 0 0 | α6 α6 0 α3 α4 0 α4 Глава 5 СВЕРТОЧНЫЕ КОДЫ 5.1 Сверточные коды и их свойства Сверточными кодами являются древовидные коды [3], на которые накладываются дополнительные ограничения по линейности и постоянстве во времени. Для сверточных кодов справедлива линейная свертка или в виде полиномов a(х) = g(х) d(х), (5.64) где ai – символы кода, gi-k – весовые коэффициенты (коэффициенты производящего полинома кода g(x)), dk – информационные символы кода. Сверточные (n,k) коды, которые иногда называют скользящими блочными кодами, обычно задаются скоростью R=k0/n0 и, в отличие от блочных кодов, требуют для своего описания несколько порождающих (производящих) полиномов. Эти полиномы могут быть объединены в матрицу , (5.65) где i=1...k0, j=1...n0, k0 и n0 - целые числа: k0 - число информационных символов, необходимых для формирования одного кадра n0 на выходе кодера. Длина скользящего слова n при данной скорости R определяется размером кадра n0 и длиной (или максимальной степенью) производящих полиномов при этом информационная длина кодового слова (5.66) Однако следует помнить, что сверточные коды являются непрерывными и деление последовательности символов кода на кодовые слова условно. Вместо длины кодового слова часто используется понятие «длина кодового ограничения» nа, которая показывает максимальное расстояние между позициями информационных символов, участвующих в формировании проверочного символа данного кода1 (например, при R =1/2 длина кодового ограничения равна числу ячеек памяти регистра сдвига кодера) nа =[max deg gij (x)+1]. (5.67) Входная последовательность из k информационных символов представляется вектором-строкой D(x) = [ di(x)] = [ d1(x), d2(x), ... dk0(x)]; а кодовое слово на выходе кодера A(x) = [aj(х)] = [ a1(x) ... an0(x)]. Операция кодирования представляется в виде произведения A(х) = D(x)×G(x) (5.68) или aj(х) =di(x) × gij(x). (5.69) Проверочная матрица H(x) должна удовлетворять условию G(x)×HT(x) = 0, (5.70) а вектор синдромов ошибки (синдромных полиномов) равен S(x) = B (x)×HT(x) = [Sj(х)] = [ S1(x) ... Sn0-k0(x)], т.е. (n0 - k0)-мерный вектор-строка из полиномов, а B(x) =A(x)+e(x), где e(x) -вектор ошибок в декодируемой последовательности B(x). Очевидно, что S(x) = [A(x)+e(x)]×HT(x) = e(x)×HT(x). (5.71) В дальнейшем будут рассматриваться только двоичные сверточные коды, для которых сложение и умножение полиномов производится над двоичным полем GF(2m). Если сверточный код является систематическим, то информационные символы на выходе кодера совпадают с информационной последовательностью на входе кодера, то есть g1(x) = 1; тогда при k0 = 1 G(x) = [ 1, g2(x), g3(x) ... gn0(x)], (5.72) а для кодов R = 1/2, G(x) = [1, g(x)]. Систематические сверточные коды всегда являются некатастрофическими, то есть всегда удовлетворяют условию, что наибольший общий делитель (НОД) производящих полиномов равен единице НОД[ g1(x) ... gn0(x)] = 1, в отличие от катастрофических, имеющих склонность к неограниченному размножению некоторых конфигураций ошибок в процессе декодирования. Такие коды могут декодироваться с помощью алгоритма Евклида [3] для полиномов, согласно которому всегда существуют полиномы с1(х) ... сn0(х) такие, что с1(х)×g1(x) + ... + сn0(x)×gn0(x) = 1. При этом кодирование осуществляется в виде aj(х) = d(x)× gj(х), i=1...n0, а декодирование d(x) = a1(x)×c1(x)+ ... + an0(х)×cn0(х). НОД двух полиномов S(x) и r(x) над полем GF(q) можно вычислить с помощью итеративного деления полиномов: если deg [S(x)] ³ deg [r(x)] ³ 0, то алгоритм вычисления НОД имеет вид S(x) = a1(x)× r(x) + r1(x), r(x) = a2(x)× r1(x) + r2(x), r1(x) = a3(x)× r2(x) + r3(x), . . . . . . . . . . rn-1(x) = an+1(x)× rn(x), процесс прекращается при получении нулевого остатка ri(х); тогда последний ненулевой остаток rn(x) = НОД [r(x), S(x)]. (5.73) Сверточные коды, скорость которых R ¹ 0,5, позволяют либо увеличить скорость кода за счет потери корректирующей способности; либо увеличить корректирующую способность кода за счет уменьшения скорости . Как уже отмечалось, сверточные коды для практического применения не должны позволять катастрофического размножения ошибок. Поэтому для кодов порождающие полиномы не должны иметь общего множителя, а для кодов не должны иметь общего множителя определители различных çk0´ n0ç подматриц. При этом обеспечивается ортогональность всех проверочных соотношений набора порождающих полиномов. Кроме того, практически целесообразно иметь в каждом из полиномов одинаковое число ненулевых членов. Качество работы декодера зависит также от длины блока декодирования – L (ширины окна декодирования); причем, чем больше блок декодирования, тем лучше. Это определяется тем, что сверточный код имеет множество минимальных расстояний, которые определяются длинами начальных сегментов кодовых последовательностей, между которыми определяется минимальное расстояние в процессе декодирования. Это расстояние равно dL – числу ненулевых символов в блоке декодирования L с ненулевым первым кадром. При этом декодер может исправить t ошибок, если 2t + 1 £ dL. Для большинства хороших сверточных кодов длина блока декодирования может быть больше или равна n. Свободным кодовым расстоянием сверточного кода называется расстояние d = max dL, (5.74) Свободное расстояние равно наименьшему весу ненулевого начального блока декодирования при L®µ. Как правило, свободное кодовое расстояние для двоичных сверточных кодов при R = k0/n0 определяется выражением (5.75) но в общем случае может быть и несколько больше. В таблице 5.1 приведены некоторые несистематические сверточные коды с максимальным свободным расстоянием [3]. Оптимальными будем считать такие коды, которые обеспечивают в заданном канале меньшую вероятность ошибок декодирования Рд при одинаковой скорости кода R=k0/n0 и одинаковой вычислительной сложности декодирования. Таблица 5.8 – Несистематические сверточные коды с большим значением кодового расстояния d Параметры кода Производящие полиномы gi(х) R n k d g1 g2 g3 g4 1/2 10 5 7 11001 10111 1/3 15 5 12 10101 11011 11111 1/4 20 5 16 10101 11011 10111 11111 Если при поиске хороших блочных кодов широко используются алгебраические методы, то для отбора близких к оптимальным сверточных кодов обычно используются различные алгоритмы просмотра большого числа кодов на ЭВМ. Можно сказать, что регулярных методов поиска сверточных кодов с большим кодовым ограничением не существует. Большинство известных в настоящее время сверточных кодов с хорошими свойствами найдено поиском на ЭВМ [3]. Сверточные коды в ряде практически важных случаев позволяют получить энергетически лучшие результаты в сравнении с блочными. В [3,8,9] приводятся результаты исследования эффективности некоторых сверточных кодов. У сверточных кодов при уменьшении скорости кода значительно медленнее обмен эффективности на удельную скорость. Современная элементная база позволяет реализовать близкие к оптимальным алгоритмы декодирования сверточных кодов с большим кодовым ограничением, что позволяет увеличить энергетический выигрыш. В сочетание с итерационными и многоступенчатыми пороговыми алгоритмами декодирования эти коды позволяют приблизиться к предельной эффективности для двоичных кодов, как при жестких, так и мягких решениях в канале [10,11]. Кроме рассмотренных выше применяются и другие способы описания сверточных кодов: – с помощью кодового дерева или решетчатой структуры; – с помощью разностных треугольников. Эти способы описания обычно используются для построения различных алгоритмов декодирования сверточных кодов и будут рассмотрены ниже. 5.2 Кодирование и декодирование сверточных кодов 5.2.1 Методы кодирования и декодирования Кодирование сверточных кодов производится аналогично блочным циклическим кодам с помощью регистров сдвига, у которых структура обратных связей определяется производящим полиномом кода. Различие только в том, что при k0 >1 сверточный код имеет несколько производящих полиномов, а кодер должен иметь соответствующее число регистров сдвига. На рисунке 5.1 приведены функциональные схемы двух кодеров для сверточных кодов R=1/2 (nа =3, d=5) и R=2/3(nа =4, d=3) [2]. Эти коды являются несистематическими; производящие полиномы кода R=1/2 представлены на рисунке. Рисунок 5.23 – Кодеры сверточных кодов а) R=1/2 и б) R=2/3 Кодеры работают следующим образом. На вход регистра сдвига кодера (а) из 3 ячеек памяти подается двоичная последовательность информационных символов, из которых с помощью регистра сдвига и сумматоров по модулю 2 формируется две двоичных последовательности. Символы этих последовательностей с помощью переключателя П поочередно подключаются к выходу кодера; скорость переключения должна быть в два раза больше скорости ввода информационных символов. Матрица производящих полиномов кода R=2/3 (рисунок 5.1б) имеет вид (5.76) Регистры сдвига 1 и 2 (число регистров равно k0) имеют по две ячейки памяти и три сумматора по модулю 2 (число сумматоров равно n0), формирующих символы кода в соответствии с видом производящих полиномов. Переключатель Пвх разделяет входные информационные символы между регистрами, переключатель Пвых формирует кодовую последовательность на выходе кодера из выходных символов сумматоров. Кодовое дерево рассматриваемого кода R=1/2, и соответствующая ему кодовая решетка имеют вид, показанный на рисунке 5.2. Кодовое дерево строится таким образом, что информационному символу «0» соответствует перемещение на верхнюю ветвь (ребро) дерева, а информационному символу «1» - на нижнюю ветвь. Можно обратить внимание, что после формирования четырех вершин (на рисунке 5.2 отмечены цифрами 0,1,2,3 в скобках) структура ветвей дерева повторяется. Это обстоятельство определяется состоянием двух последних ячеек памяти регистра сдвига кодера (00,01,10,11); в общем случае число состояний зависит от кодового ограничения кода и равно . Решетка сверточного кода представляет состояния кодера в виде четырех уровней, а ветви дерева являются ребрами решетки, в результате чего избыточные части дерева отождествляются. Такое представление кода является более удобным при разработке и описании процессов декодирования. Рисунок 5.24 – Кодовое дерево и решетка сверточного кода R=1/2, кодовое ограничение na=3 Если сверточный код является систематическим, то g1(x) = 1 (в верхней ветви кодера рисунка 5.1а отсутствует член суммы x2) и информационная последовательность становится частью выходной последовательности без кодирования, что упрощает в последующем процесс ее декодирования. Для декодирования сверточных кодов используются, в основном, три метода [2,3]: декодирование по алгоритму Витерби, синдромное декодирование и последовательное декодирование. Декодирование по алгоритму Витерби и последовательное декодирование являются оптимальными по критерию максимального правдоподобия (МП) и широко используются для двоичных сверточных кодов с малой длиной кодового ограничения в каналах с жестким и мягким решениями. Методы синдромного декодирования могут оптимизироваться по критерию МП и основаны на вычислении и последующем анализе синдрома ошибок, что делает их похожими на соответствующие методы декодирования циклических кодов (декодирование с табличным поиском и пороговое декодирование). Известно, что пороговое декодирование возможно для относительно ограниченного класса сверточных кодов [10], позволяющих построить ортогональные проверки относительно контролируемого (проверяемого) символа e0u. В настоящее время получено множество хороших кодов, состоящее из канонических самоортогональных кодов (КСОК) и кодов, допускающих ортогонализацию, в том числе сверточных кодов, полученных на ЭВМ методом проб и ошибок. Списки таких кодов приведены в работах [2,5,10,12,13]. Для построения и описания ортогональных сверточных кодов широко применяется метод, использующий понятие разностного треугольника [2]. Поясним этот метод на примере, учитывая, что большинство таблиц самоортогональных и ортогонализируемых кодов составлены в виде разностных треугольников. Разностный треугольник (пример 5.1) представляет собой треугольный массив, вычисленный по первой строке проверочной матрицы HT так, что ij-й элемент треугольника равен разности между номерами столбцов, в которых (i+j)-й и j-й символы этой строки равны 1. Пример 5.1 Построим разностный треугольник сверточного кода (406,203), R=1/2, который в дальнейшем часто используется в качестве примера в практических приложениях. Решение: 7 20 49 37 24 18 1 14 32 27 69 86 61 42 19 15 46 76 106 110 79 43 33 47 113 130 128 80 57 65 Dp = 137 148 129 94 89 155 149 143 126 156 163 175 170 195 202 Заметим, что в этом треугольнике нет одинаковых чисел, а первый столбец представляет собой запись степеней производящего полинома этого кода g(x)=1+x7+x27+x76+x113+x137+x155+x156+x170+x202; C другой стороны , где , D1j – элемент первой строки разностного треугольника. Для построения кода достаточно знать первую строку разностного треугольника. Первая строка проверочной матрицы HT202 соответствует полиному g(x), записанному в двоичной форме; остальные строки образуются сдвигами первой строки g(x)× xi, i =1...m (при этом степени gi(x) суммируются по mod m). Используя разностный треугольник легко записать систему ортогональных проверок для данного кода, см. пример 5.2. Пример 5.2 Для кода в примере 5.1 множество ортогональных проверок (элементов синдрома ошибки) относительно проверяемого символа ошибки eku (в k-ом информационном символе) записывается следующим образом Sk =eku + euk-7 + euk-27 + . . . +euk-202 + ekp, Sk+7 =euk+7 + eku + euk-20 + euk-69 + . . . +euk-195 + epk+7, Sk+27 =euk+20 + euk+27 + eku + euk-49 + euk-86 + . . . +euk-175 + epk+27, Sk+76 =euk+49 + euk+69 + euk+76 +eku + euk-37 + euk-61 +…+euk-126 + epk+76, Sk+113 =euk+37 + euk+86 + . . . +eku + euk-24 + . . . +euk-89 + epk+113, Sk+137 =euk+24 + euk+61 + . . . +eku + euk-18 + . . . +euk-65 + epk+137, Sk+155 =euk+18 + euk+42 + . . . +eku + euk-1 + . . . +euk-47 + epk+155, Sk+156 =euk+1 + euk+19 + . . . +eku + euk-14 + euk-46 + epk+156, Sk+170 =euk+14 + euk+15 +. . . +euk+170 + eku + euk-32 + epk+170, Sk+202 =euk+32 + euk+46 + . . . +euk+202 + eku + epk+202, где Sk+j – элементы синдрома ошибки для k-го информационного символа, j – степени производящего полинома g(x), euk+j - символ ошибки в (k+j)-м информационном символе, epk+j - символ ошибки в (k+j)-м проверочном символе. Множество проверок в примере 5.2 показывает, что рассматриваемый сверточный код является каноническим самоортогональным кодом, так как никакие два проверочных уравнения не содержат более одного общего символа (в данном случае это символ eku ). Код не будет каноническим самоортогональным, если для формирования ортогонализации проверочных уравнений необходимо использовать линейные комбинации элементов синдрома. Общее число проверочных уравнений (ортогональных проверок) определяется числом ненулевых элементов производящего полинома. В данном случае J=10 (кодовое расстояние d=J+1), что позволяет мажоритарным методом правильно декодировать k-й информационный символ, если число ошибок в символах, участвующих в проверках, не более пяти. В общем случае, когда R = k0 /n0, набор порождающих полиномов кода должен быть таким, чтобы все элементы разностных треугольников были различны (пример 5.3). Причем существует двойственность между кодами и , что позволяет использовать для построения этих кодов одинаковые порождающие полиномы. Систематический сверточный код с получается в виде: – проверочная последовательность символов, (5.77) , i=1,2,..., n0-1 – информационные последовательности, где di(x) – информационные последовательности символов на входе кодера. Пример 5.3 Для систематического сверточного кода R=2/3 (или 1/3), с числом проверок J=6, разностные треугольники имеют вид: , а первые строки этих треугольников задают порождающие полиномы: g1(x) = 1 + x14 + x21 + x23 + x36 + x39, g2(x) = 1 + x8 + x27 + x28 + x32 + x38 . Разностные треугольники не имеют одинаковых элементов, а производящие полиномы одинаковых степеней x,кроме x0. Систематический сверточный код с R = 1 /n0 может строится с использованием этих же производящих полиномов, но теперь для одной информационной последовательности вычисляется (n0-1) проверочная последовательность символов; a1(x) = d1(x), ai(x) =gi(x)× di(x), i=1,2,...n0-1. (5.78) Пример 5.4 Проверочная матрица сверточного кода R = 1/3 из примера 5.3 имеет вид: HT= Число столбцов подматрицы HT в примере 5.4 равно 40, что соответствует (+1). Первая строка этой матрицы содержит единицы в 12 столбцах, следовательно, можно записать 12 ортогональных проверочных соотношений и вычислить 12 элементов синдрома ошибки {S0, S14, S21, S23, S36, S39, S40, S48, S67, S68, S72, S78}. Это позволяет исправить ошибку в проверяемом информационном символе при искажении до 6 символов, участвующих в проверках. Кодовое расстояние кода d=2J+1 = 12. Следовательно, для кодов R=1/n0 число проверочных соотношений Jå = (n0-1)×J, (5.79) а кодовое расстояние d=Jå+1. (5.80) Подматрицы проверочной матрицы в процессе декодирования могут использоваться отдельно для формирования двух синдромных полиномов ошибки: S1(x), S2(x) (и более, если n0>3), а для исправления ошибки в этом случае может применяться мажоритарная процедура на уровне обнаружения (или необнаружения) ошибки каждым из синдромных полиномов. Усеченная проверочная матрица кода из примера 5.3 для скорости R=(n0-1)/n0=2/3 может быть записана в виде порождающего полинома g1(x) в двоичной форме, а седьмая строка в виде порождающего полинома g2(x) в двоичной форме (пример 5.5). Пример 5.5 Проверочная матрица сверточного кода R=2/3 из примера 5.3 имеет вид: Число столбцов матрицы в примере 5.5 равно максимальной степени набора порождающих полиномов +1. Первая строка матрицы содержит единицы в шести столбцах (число ненулевых элементов полинома g1(x)), что позволяет записать шесть ортогональных проверочных соотношений для вычисления шести элементов синдрома ошибки {S0, S14, S21, S23, S36, S39} – для исправления ошибок в первой информационной последовательности; седьмая строка матрицы содержит единицы также в шести столбцах и позволяет вычислить шесть элементов синдрома {S0, S8, S27, S28, S32, S38} для исправления ошибок во второй информационной последовательности. Кодовое расстояние для кодов R=(n0-1)/n0 определяется, как и для R=1/2 d=J+1. (5.81) Однако, в сравнении с кодом R=1/2, происходит ухудшение качества декодирования из-за увеличения числа информационных символов в проверочных соотношениях. В приложении Б приведен список полиномов, которые могут быть использованы в качестве порождающих как для сверточных кодов R=1/2, так и для кодов R¹1/2. Необходимый набор порождающих полиномов формируется с учетом рекомендаций, сформулированных выше. 5.2.2 Декодирование по алгоритму Витерби Алгоритм декодирования Витерби сверточного кода R=1/2 (кодер приведен на рисунке 5.1а, а кодовое дерево и решетчатая диаграмма на рисунке 5.2) показан на рисунке 5.3. Рисунок 5.25 – Алгоритм декодирования сверточного кода R=1/2 Декодирование производится словами по k пар двоичных символов канала. В блоке 1 эта последовательность преобразуется в четверичную последовательность (0,1,2,3) по количеству состояний кодера: 22 (основание кода в степени, равной старшей степени производящего полинома). Декодирование производится по алгоритму Витерби [2]. Для реализации этого алгоритма k должно быть существенно больше кодового расстояния. В блоках 2 и 3 производится оценка состояний кодера, вычисление и сохранение, относительно этих состояний, метрики четырех путей изменения состояний с учетом символов канала; при этом в соответствии с метрикой по мере увеличения i всегда сохраняются только 4 (из 8 возможных) выживших пути (ближайшие к декодируемой последовательности). Далее, после обработки всех k символов канала первого кодового слова, начинается обработка символов второго кодового слова и, одновременно, в блоке 4 по выжившим путям вычисляется окончательная оценка состояний кодера и определяются все k информационных символов предыдущего кодового слова. В блоке 5 формируется двоичная последовательность декодированных информационных символов в N информационных слов для статистической обработки. В примере 5.6 показан процесс декодирования по алгоритму Витерби при исправлении конкретной ошибки. Если на вход декодера поступает неисправляемая данным кодом конфигурация ошибок, то выжившим чаще всего оказывается ошибочный путь, что приводит к ошибочному декодированию информационной последовательности. Однако, как правило, ошибочный путь мало отличается от правильного и через несколько шагов алгоритма при отсутствии ошибок на входе правильный путь восстанавливается. Пример 5.6 Декодирования по алгоритму Витерби R=1/2 Рассмотрим алгоритм Витерби на примере исправления заданной конфигурации ошибок сверточным кодом R=1/2, кодер, кодовое дерево и кодовая решетка которого показана на рисунках 5.1 и 5.2. Предположим, что передавалось нулевая кодовая последовательность вида {00 00 00 00 …}, а принятая последовательность на выходе демодулятора с жестким решением имеет вид {10 00 10 00 00 …} (произошло две ошибки в информационных символах). Такая конфигурация ошибок должна исправляться, поскольку кодовое расстояние данного кода равно 5. Ниже в данном примере показана серия решетчатых диаграмм, показывающих состояние решетки после 2, 3, 4, 9 и 10 циклов алгоритма. Числа, поставленные в вершинах, указывают расстояние Хэмминга (выделены жирным шрифтом), накопленное «выжившим» путем в этой вершине;«выжившие» пути показаны сплошными линиями, «невыжившие» пути – пунктиром. Ребра графа обозначены двойными цифрами обычным шрифтом. На первом и втором шагах алгоритма (диаграмма а)) произошла первая ошибка в канале и «выжившими» являются все 4 пути. На третьем шаге произошла вторая ошибка в канале (диаграмма б)), каждый из путей раздвоился и сохранился лишь лучший путь, метрика которого в меньшей степени отличается от принятой последовательности (показана в нижней части каждого рисунка). Общее число сохранившихся путей вновь становится равным 4 по числу вершин графа. Этот процесс повторяется после приема следующей пары символов. Поскольку во входной последовательности другие ошибки не наблюдаются, после пятого шага (диаграмма в)) видно, что метрика первого пути имеет лучшие значения в сравнении с метриками других путей. Из этой диаграммы, а также диаграмма г), видно, что выживающие пути могут отличаться друг от друга в течение большого числа шагов алгоритма. Однако на десятом шаге (диаграмма д)) первые восемь ребер всех выживших путей совпадают. В этот момент можно принимать решение о переданных информационных символах на первых шагах алгоритма (на выход декодера выдается самый старый информационный символ выжившего пути). Число шагов алгоритма, когда происходит слияние выживших путей, является случайной величиной, зависящей от конфигурации ошибок в канале. Поэтому при практической реализации декодера устанавливают фиксированное число шагов алгоритма, после которых начинается считывание самых старых информационных символов, поступивших на вход. Если к этому шагу в декодере сохранилось больше одного пути, то на выход выдается информационный символ одного из выживших путей (например, самого верхнего по решетке или с самой лучшей метрикой). а) б) в) г) д) Основные трудности при реализации алгоритма Витерби определяются тем, что сложность декодера экспоненциально растет с увеличением кодового ограничения (число состояний декодера равно 2n-1); поэтому значение кодового ограничения кодов, применяемых на практике, не превышает nа£15. Недвоичные коды декодировать алгоритмом Витерби еще сложнее. В кодеках сверточных кодов с декодированием по алгоритму Витерби, в основном, используются несистематические коды, так как они позволяют при малом кодовом ограничении получить большее свободное расстояние по сравнению с систематическими. При этом учитывается, что сложность декодирования тех и других кодов примерно одинакова. Декодирование по алгоритму Витерби кода R=2/3 (кодер показан на рисунке 5.1б) оказывается существенно сложнее по сравнению с кодами R=1/2. В каждую вершину кодовой решетки будет входит теперь не два пути, а четыре и для определения выживших путей необходимо производить восьмеричное сравнение. В общем случае для кодов R=k0/n0 требуется 2k0-ичное сравнение, что приводит к значительным усложнениям практической реализации декодеров. С целью упрощения алгоритма декодирования сверточные коды R=(n0-1)/n0 получают выкалыванием кодов R=1/2. Например, код R=2/3 можно получить из кода R=1/2 (кодер показан на рисунке 5.1а), выкалыванием каждого второго символа на выходе первого сумматора (тогда на выход кодера будут поступать 1,2,4,5,6,8,9,10,12, … и т.д. символы, сформированные кодером). Для получения кода R=3/4 из этого же кода выкалывается каждый третий символ, сформированный кодером, и на выход поступают, соответственно, 1,2,4,5,7,8,10, … символы. Выколотые коды имеют почти те же характеристики, что и лучшие известные ранее коды R=k0/n0. При декодировании выколотых кодов по алгоритму Витерби выколотые ребра решетки воспринимаются как стирания этих ребер в канале, соответственно уменьшается кодовое расстояние для исправления ошибок и увеличивается размер кадра. Сложность декодирования выколотых кодов, хотя и увеличивается, но в гораздо меньшей степени, так как сохраняется логика двоичных сравнений исходного кода. Можно построить единый кодек, как для исходного кода, так и для выколотых на его основе, в котором производится некоторая перестройка логики в зависимости от скорости кода. Сверточные коды R=1/n0 строятся аналогично кодам R=1/2, но имеют большее кодовое расстояние и кодовое ограничение. В кодере вместо двух сумматоров по модулю 2 на выходе ставится n сумматоров. Например, кодер R=1/3 должен иметь три сумматора по модулю 2 на выходе по сравнению со схемой, показанной на рисунке 5.1а. В качестве дополнительного производящего полинома g3(x) может быть взят g1(x) или g2(x). Изменения алгоритма Витерби состоят в том, что метрики на ребрах решетки вычисляются из расчета n0 символов на ребре вместо двух. Число состояний решетки остается тем же. 5.2.3 Последовательное декодирование В отличие от алгоритма Витерби при последовательном декодировании производится продолжение и обновление метрики только одного пути, который представляется наиболее вероятным, при этом делается попытка принять решение о декодируемом символе, принятом в начале пути. Если решение о декодируемом символе, находящемся в начале пути, принять невозможно, то производится либо движение вперед, т.е. прием очередного символа и обработка метрики данного пути, или возврат назад (выбор другого пути), если значения метрики увеличиваются. Процедура продолжается до тех пор, пока не будет принято решение о декодировании символа, расположенного в начале пути. Основное достоинство последовательного алгоритма заключается в том, что в среднем длина пути, достаточная для правильного декодирования меньше, чем у алгоритма Витерби. Недостатки определяются тем, что длина пути, приводящего к правильному декодированию, является случайной величиной. Это вызывает затруднения при реализации декодера, так как нельзя определить заранее какой объем памяти потребуется для сохранения метрики рассматриваемого пути, а это значит, что всегда существует вероятность переполнения памяти и сбой декодера. В практике построения последовательных декодеров применяются два варианта алгоритма последовательного декодирования, позволяющих получить приемлемые для реализации сложность декодирования и объем памяти: алгоритм Фано и стек-алгоритм. Алгоритм Фано работает с малыми значениями длин кодового ограничения. Стек-алгоритм более прост для понимания и реализации на микропроцессорах, но требует несколько большего объема памяти. Структурная схема стек-алгоритма показана на рисунке 5.4, где L0 значение метрики пути в исходном состоянии. Декодер создает стек [2], состоящий из просмотренных ранее путей (могут иметь различную длину) и упорядочивает их в соответствии со значением метрики. На каждом шаге продолжается путь, находящийся наверху стека, что порождает 2k0 новых путей со своей метрикой. Затем стек опять упорядочивается. Процедура продолжается до тех пор, пока длина пути, находящегося наверху стека, не станет равной длине декодируемой последовательности. Рисунок 5.26 – Блок-схема стек-алгоритма Пример 5.7. Дано: передаваемая информационная последовательность I(x)=100, код скорость кода R=1/2, k=3, производящие полиномы коды g1(x)=1+x+x2, g2(x)=1+x2, последовательность ошибок e(x)=010000. Найти: оценку переданного слова с использованием стек-алгоритма декодирования сверточных кодов. Решение: переданная кодовая последовательность равна A(x)=110111. С учетом последовательности ошибок e(x) принятое слово имеет вид B(x)=100111. Декодирование осуществляется за несколько шагов, см. рисунок 5.5, где состояния представляют собой возможные состояния триггеров регистра кодера R1(x) и R0(x), ветви соответствуют выходам кодера C1(x) и C0(x). После каждого состояния показана метрика ветви. Метрика последней ветви данного пути соответствует метрике пути. Принятая последовательность: B=10.01.11 B=10.01.11 B=10.01.11 B=10.01.11 Стек «оценка информационной последовательности – метрика пути»: • 0 – 1 • 1 – 1 • 1 – 1 • 00 – 2 • 01 – 2 • 10 – 1 • 00 – 2 • 01 – 2 • 11 – 3 • 100– 1 (декод.) • 00 – 2 • 01 – 2 • 101– 3 • 11 – 3 Рисунок 5.27 – Декодирование по стек-алгоритму Наиболее сложной операцией в рассматриваемом алгоритме является необходимость упорядочивания стека на каждом шаге декодирования, причем требуемая емкость стека является случайной величиной. Кроме того, для данного алгоритма запрещено производить нормировку метрик путей, что дополнительно увеличивает требования к памяти вычислительной системы, участвующей в декодировании. Выводы: • Последовательное декодирование позволяет использовать большие значения длины кодового ограничения (на практике, 100>K>10), что повышает помехоустойчивость приема. • Продолжительность декодирования зависит от значения отношения сигнал/шум. • Стек-алгоритм применяется в приложениях с низкой скоростью передачи, возможна реализация декодера практической системы в программном исполнении. Синдромное декодирование Синдромное декодирование сверточных кодов, в принципе, не отличается от синдромного декодирования циклических кодов. Вначале декодер по принимаемой последовательности символов вычисляет вектора синдромов ошибки (5.6), когда R¹1/2, или один синдром ошибки, когда R=1/2. Затем путем анализа синдромов определяется вектор (или символ) ошибки и производится коррекция соответствующих информационных символов входной последовательности. Практически используются, в основном, два метода синдромного декодирования: • декодирование с табличным поиском, • пороговое декодирование. Декодирование с табличным поиском заключается в том, что вычисленный синдром ошибки сравнивается с таблицей всевозможных синдромов ошибок данного кода, для каждого из которых символ ошибки заранее определен. После обнаружения подобного синдрома в таблице остается только выполнить коррекцию информационной последовательности. Очевидно, что декодирование с табличным поиском (как и аналогичное декодирование циклических кодов) практически можно применять только в тех случаях, когда объем таблицы ограничен, иначе декодер получается слишком сложным. Это сверточные коды с малым кодовым ограничением (nа £ 10 ¸ 20) и, соответственно, малым энергетическим выигрышем (1 ¸ 2,5 дБ). 5.2.4 Пороговое декодирование сверточных кодов Наиболее перспективными в смысле благоприятного сочетания качества декодирования и сложности реализации являются пороговые (в частных случаях мажоритарные) алгоритмы декодирования [10,11,14] сверточных кодов. В различных модификациях порогового алгоритма декодирования вычислительная сложность слабо зависит от кодового ограничения, а определяется либо кратностью исправляемых ошибок на длине n, либо числом проверочных соотношений, используемых для исправления ошибок. Пороговое декодирование возможно для определенного (хотя и достаточно широкого) класса линейных кодов как блочных, так и сверточных, позволяющих получить так называемые разделенные (или ортогональные) проверки на четность (раздел 5.2.1). Число проверочных уравнений J и число исправляемых ошибок t связаны соотношением J ³ 2t, кодовое расстояние d = J + 1. Пороговое декодирование во многих случаях не является оптимальным (в смысле вероятности ошибки декодирования) в сравнении с последовательным декодированием. Однако, в практически важных случаях, особенно в каналах с переменными параметрами, эффективность некоторых модификаций пороговых декодеров может быть достаточно высокой. Алгоритмы порогового декодирования в сочетании с кодами, имеющими малую плотность проверок на четность, являются более гибкими в каналах с пакетирующимися ошибками. Это, например, итерационные алгоритмы [10,14,15], алгоритмы многоступенчатого порогового декодирования и др., которые за счет внутреннего перемежения и итераций позволяют исправлять большие пакеты ошибок. В каналах с известной статистикой шума пороговые декодеры могут эффективно использовать мягкие решения. Как видно из системы уравнений (пример 5.2), самоортогональный код не требует устранения влияния предыдущих решений декодера для получения системы ортогональных проверок, то есть возможно детерминированное декодирование и каждый элемент синдрома ошибки образуется в результате суммирования одинакового числа символов ошибок ek. Множество элементов синдрома {Sk, Sk+7, . . ., Sk+202} задает множество проверок {Sl}, l=1,2,…,J, ортогональное относительно символа ошибки euk в k-ом информационном символе. Множество {Sl} может быть использовано для порогового (мажоритарного) декодирования в соответствии с правилом: если , тогда eku = 1, иначе eku = 0. (5.82) Структурная схема порогового декодера, реализующего данное правило решения показана на рисунке 5.6. Последовательность символов канала bk после разделения на информационные buk и проверочные bpk поступает в регистр синдрома, где производится вычисление элементов синдрома Sk . В анализаторе синдрома формируются ортогональные проверки Sl (l=1…J), сумма которых в пороговом устройстве сравнивается с уровнем порога и определяется значение символа ошибки ek . Рисунок 5.28 – Структурная схема порогового декодера Исправление ошибки происходит в сумматоре по модулю два, на второй вход которого подаются информационные символы канала из запоминающего устройства, выполняющего функцию хранения этих символов на время вычисления символа ошибки. К достоинствам порогового декодера относится возможность его реализации на скоростях передачи, практически равных скорости работы элементной базы, используемой для построения декодера. Качество порогового декодера можно улучшить, если ввести обратную связь (на рисунке 5.6 показана пунктиром), через которую решение декодера подается в анализатор синдрома и устраняет влияние ошибки данного символа на декодирование следующего символа. При декодировании с обратной связью кодовое расстояние dL больше, чем при детерминированном декодировании (без обратной связи) и ближе к значению свободного кодового расстояния d, так как при детерминированном декодировании в определении dL участвует существенно большее число информационных символов в предшествующих последовательностях. Как известно [3], лучшие сверточные коды способны исправлять пакеты ошибок ( или количество ошибок), длина которых численно равна половине количества проверочных символов на длине кодового блока. При пороговом декодировании с обратной связью система ортогональных проверок (см. пример 5.2) упрощается и принимают вид Sk = eku + ek p, Sk+7 = eku + euk+7 + epk+7, Sk+27 = eku + euk+20 + euk+27 + epk+27, Sk+76 = eku + euk+49 + euk+69 + euk+76 + epk+76, Sk+113 = eku + euk+37 + . . . euk+113 + epk+113, Sk+137 = eku + euk+24 + euk+61 + . . . +euk+137 + epk+137, Sk+155 = eku + euk+18 + euk+42 + . . . +euk+155 + epk+155, Sk+156 = eku + euk+1 + euk+19 + . . . +euk+156 + epk-156, Sk+170 = eku + euk+14 + euk+15. . . +euk+170 + epk+170, Sk+202 = eku + euk+32 + euk+46 . . . +euk+202 + epk+202 . (5.83) Кроме самоортогональных сверточных кодов пороговое декодирование допускает широкий класс сверточных кодов, полученных с помощью ЭВМ методом проб и ошибок, например, ПО-коды [10]. Для получения J ортогональных проверок ПО-коды обычно требуют сложения нескольких символов синдрома ошибки, но при этом иногда получаются существенно лучшие коды (необходимое число проверок получается на меньшей длине кодового ограничения), особенно при декодировании с обратной связью. При пороговом декодировании вероятность ошибки декодирования pд минимальна, если используется правило решения по максимуму апостериорной вероятности (правило МАВ). Для двоичного симметричного канала c вероятностью ошибки p эта вероятность определяется неравенством [10] . (5.84) В алгоритме декодирования по правилу МАВ (в некоторых источниках, например [2], алгоритм АРР) неравенство (5.16) принимает вид , то ek = 1, (5.85) где Wl – весовые коэффициент, пропорциональные надежности l-той проверки. . (5.86) В [10] показано, что правило МАВ (АВ декодер) требует, чтобы , (5.87) где pl – вероятность того, что в проверке Sl нечетное число символов (кроме euk) принимает значение 1. , , (5.88) где pj – вероятность появления единицы в последовательности e1,e2,...ek,... в предположении, что элементы последовательности искажаются независимо; nl – объем проверки Sl. В частном случае, когда канал является стационарным или стационарным на длине кодового ограничения, pj = p, а . (5.89) В каналах с переменными параметрами весовые коэффициенты являются функциями времени. Каждая величина Wl является нелинейной функцией объема проверки nl и вероятности ошибок декодируемых символов pj, которая в свою очередь зависит только от уровня сигнала на выходе демодулятора, осуществляющего мягкое решение. Реализация порогового декодера в этом случае существенно усложняется. Веса Wl могут быть вычислены либо с помощью нелинейного отображения с использованием аналоговых регистров сдвига, либо с помощью приближенного метода АРР [2], использующего цифровое представление сигнала на выходе демодулятора и цифровые регистры сдвига. Практические исследования показывают, что для получения результатов, близких к оптимальному декодированию, достаточно восьми уровней квантования. Однако необходимо отметить возможность упрощения рассмотренного выше алгоритма в каналах со стираниями (трехуровневый канал). В этом случае все проверочные уравнения, содержащие стертые символы, не учитываются в системе проверок {Sl}, решение принимается только по оставшимся проверкам, веса которых приравниваются к единице. Возможные при этом ошибочные решения уточняются путем итераций. Повторное декодирование (итерация) позволяют уменьшить вероятность ошибки декодирования. При этом для итераций может использоваться тот же декодер или несколько декодеров (многоступенчатый декодер) в зависимости от необходимой скорости работы декодера в канале. В первом случае декодер обычно называют итерационным, а во втором – многоступенчатым [11]. Физическая реализация и конкретный анализ алгоритмов итерационного и многоступенчатых декодеров будут рассмотрены ниже. Недостатком декодирования с обратной связью является эффект распространения (размножения) ошибок в некоторых пороговых декодерах сверточных кодов. Размножение ошибок наблюдается при ухудшении качества канала, когда происходит засорение анализатора синдрома ложными коррекциями по цепи обратной связи из-за неправильных решений декодера в канале с большим уровнем помех. Эффект размножения ошибок слабо проявляется в мягком декодере и в большей степени в жестком декодере. Для ослабления эффекта размножения ошибок необходим соответствующий выбор кода и применение специальных мер, уменьшающих вероятность неправильных решений декодера или ослабляющих это влияние. Этой проблеме уделяется много внимания в специальной литературе [2,9,11,12 и др.]; однако и до настоящего времени она является актуальной. Возможные пути модификации пороговых декодеров, позволяющих ослабить эффект размножения ошибок и, следовательно, расширить способность декодера исправлять ошибки в каналах с большим уровнем помех рассматриваются ниже. Чем меньше плотность проверок (меньше проверок на длине кодового ограничения), тем в меньшей степени проявляется эффект размножения ошибок и пороговый декодер может нормально работать при большей плотности ошибок на входе. Для реализации корректирующей способности сверточного кода при малой плотности проверок необходимо многократное декодирование (итерации). Практически необходимое число итераций при заданной вероятности ошибки декодирования зависит от выбора кода, алгоритма итераций и выбора параметров декодера на каждой итерации. В итерационных пороговых декодерах вероятность ошибки декодирования, по крайней мере, при достаточно малой вероятности ошибок на входе, стремится к нулю. Поэтому жесткий пороговый декодер с итерациями при соответствующем выборе параметров кода и декодеров может быть альтернативой мягкому пороговому декодеру; тем более, что мягкий декодер обычно эффективен только при полной априорной информации о статистических характеристиках сигналов и помех в канале связи. Найдем оценку в итерационном декодере на i-ой итерации для k-го символа. Если известно правило решения, то (5.90) где M{*} означает необходимость усреднения по всем значениям Wl в канале с переменными параметрами; в канале с постоянными параметрами Wl не изменяются. Первый член суммы (5.24) определяет вероятность пропуска ошибочного символа (eku = 1), второй - вероятность обнаружения (и исправления) ошибки, когда в канале ошибки не было (eku = 0). В тех случаях, когда канал стационарен на интервале, превышающем кодовое ограничение, можно считать, что на интервале стационарности , (5.91) а , (5.92) при i = 0, pд(i) = p (вероятность ошибки в канале). Следовательно, Wl = f(pд(i), nl, i,), (5.93) т.е. весовые коэффициенты изменяются с увеличением номера итерации. Заметим, что согласно (5.22) увеличение Wl можно компенсировать соответствующим изменением уровня порога T. Для определения направления изменения Т с учетом стационарности канала перепишем выражение (5.29) в виде (5.94) Используя (5.31), можно найти условия, при которых , и, следовательно, итерации уменьшают вероятность ошибки на выходе декодера (5.95) Вероятность того, что при eku = 1 ошибка обнаружится и будет исправлена, равна вероятности четного числа "1" в ошибочных символах (кроме eku ) l-го проверочного уравнения , а вероятность того, что при eku = 0 ошибка обнаружится и будет принято неверное решение об исправлении ошибки, равна вероятности нечетного числа "1", в l-ом проверочном уравнении . (5.96) Таким образом, в этом уравнении речь идет о суммировании независимых случайных величин, вероятности которых равны соответственно pl(i) и gl(i)=1-pl(i). Суммирование затруднено тем, что распределение вероятностей этих величин в общем случае неизвестно, а применение центральной предельной теоремы теории вероятностей невозможно из-за небольшого (чаще всего) числа суммируемых величин и большого отличия значений этих величин. Для решения аналогичных уравнений обычно используется метод производящих функций. Для двоичного симметричного канала производящая функция для произведения (Wl ×Sl ) равна . (5.97) Производящая функция равна произведению Gl(x) . (5.98) Тогда неравенство (5.28) можно переписать в виде , (5.99) где суммируются Gl -коэффициенты в G(x) тех членов производящей функции, у которых степени при x больше T, так как каждый коэффициент в производящей функции, это вероятность того, что рассматриваемая случайная величина равна показателю при x. При этом вероятность ошибки декодирования равна . (5.100) Коэффициенты Gl(i)/(eku = 1) и Gl(i)/(eku = 0) отличаются тем, что в производящей функции (5.30) pl и gl – меняются местами. Выражение (5.33) можно существенно упростить, если принять, что декодер является жестким и все Wl = 1 (как будет показано ниже жесткий декодер с итерациями может быть альтернативой мягкому декодеру). Тогда , . (5.101) В этом случае , (5.102) где из вероятности ошибок на (i-1)-й итерации вычисляется вероятность обнаруженных ошибок и прибавляется вероятность ложного обнаружения и исправления ошибок. Следовательно , если выполняется неравенство (5.103) После преобразования получаем (5.104) Следовательно, с уменьшением pl(i), а значит и вероятности ошибки в канале связи p, уровень порога Т можно уменьшать. Очевидно, что min {} будет иметь место в том случае, если первый член суммы удовлетворяет неравенству . (5.105) Учитывая, что и [2(T + 1) - J] > 1, . (5.106) Неравенство (5.43) показывает, что в пороговом декодере значение порога может быть (при достаточно малых вероятностях ошибки в канале) даже меньше, чем это требует мажоритарное правило решения, согласно которому T=J/2. Однако с учетом того, что Т является ближайшим целым числом, при малых J значения порога будут одинаковыми. С другой стороны на первых итерациях, когда вероятность ошибки достаточно велика, уровень порога следует устанавливать больше T>J/2, что позволит уменьшить для следующей итерации. В таком подходе к итерационному декодированию имеется глубокий смысл, заключающийся в том, что увеличение порога на первых итерациях позволит увеличить исходную вероятность ошибки p, при которой еще не проявляется эффект размножения ошибок. На рисунке 5.7 показан характер зависимости вероятности ошибки декодирования от вероятности ошибок в канале p. Численные значения, рассчитанные для сверточного кода R=1/2 по формуле (5.39) для порогового декодера и для AB-декодера (одна итерация), приведены в таблице 5.2. 1. ДК без кодирования; 2. АВ декодер; 3. Пороговый декодер Рисунок 5.29 – Зависимость pд=f(p) Таблица 5.9 – Значения вероятности ошибок декодирования pд при различных уровнях порога, одна итерация P Пороговый декодер, R=1/2, J=10 АВ-декодер T=9 T=8 T=7 T=6 T=5 0,31 0,308 0.309 0,31 0,327 0,38 0,279 0,21 0,207 0,206 0,2 0,21 0.27 - 0,13 0,128 0,121 0,105 0,1 0,135 0,059 0,09 0,0836 0,077 0,058 0,043 0,06 - 0,031 0,023 0,013 5×10-3 1,4×10-3 1,2×10-3 4,4×10-4 0,013 5,8×10-3 1,8×10-3 3,2×10-4 3,8×10-5 1,7×10-5 6,4×10-6 9×10-3 2,6×10-3 7×10-4 8,7×10-5 7,3×10-6 2,3×10-6 - 9×10-4 2,8×10-5 9,5×10-7 1,2×10-8 10-10 3,6×10-12 2×10-12 9×10-5 2,56×10-7 9×10-9 1,3×10-12 10-15 3,7×10-18 - Из рисунка 5.7 и таблицы 5.2 видно, что пороговый декодер с жестким решением размножает ошибки, когда p >PП в отличие от декодера АВ. Причем предельная вероятность PП зависит не только от параметров кода, но и от характеристик кода и декодера, в частности от значения порога T. Вероятность ошибки декодирования порогового декодера стремится к нулю при увеличении числа итераций, если , (5.107) Процесс итераций показан на рисунке 5.7 пунктиром. Этот процесс сходится согласно критерию сходимости Коши в точке [0, 0], когда p< PП и в точке [0,5; 0,5], когда p > PП, так как при p < PП и при p>PП; причем точка [PП, PП] является точкой неустойчивого равновесия. Теоретические и экспериментальные исследования показывают, что при p< PП, что характерно для итераций с постоянным порогом. Зависимость ЭВК=f(p ) для декодера АВ, итерационного модифицированного порогового алгоритма и порогового алгоритма декодирования без итераций показана на рисунке 5.11. 1.одна итерация; 2.пять итераций при Т=J/2; 3.пять итераций при T1-5=95 Рисунок 5.32 – Зависимость pд=f(p) Расчеты выполнены для когерентного приема сигнала ЧМ и сверточного кода (406,203). Для итерационного алгоритма учтена поправка DP, рассчитанная по формуле в примере 5.8. Декодеры: 1. АВ; 2. пороговый; 3. пороговый, пять итераций; 4. пороговый, пять итераций с поправкой P; 5. теоретический предел. Рисунок 5.33 – Зависимость ЭВК от вероятности ошибки в канале Видно, что поправка DP существенно уменьшает предельную вероятность PП и уменьшает выигрыш от итераций. В области относительно малых вероятностей p поправка DP фактически определяет предельно достижимое качество декодирования в итерационном пороговом декодере. При этом ЭВК значительно больше, чем в декодерах АВ и пороговом декодере без итераций. Кривая 5 на рисунке 5.10 показывает предельно достижимый выигрыш двоичных сверточных кодов при R=0,5, допускающих пороговое декодирование. Глава 6 КАСКАДЫЕ КОДЫ 6.1 Последовательные каскадные коды Из теории кодирования известно большое число корректирующих кодов и соответствующих им алгоритмов декодирования. Однако при попытке практической реализации таких кодов в каналах с высокой вероятностью ошибки часто оказывается, что сложность кодека сводит на нет преимущества высокой исправляющей способности кода. Как следует из теории информации, для наилучшего приближения к пропускной способности канала необходим случайный выбор кодовых слов при их достаточно большой длине. Практической целью является поиск кодов с большой эквивалентной длиной блока и структурой, допускающей приемлемую физическую реализацию декодера. Поставленным условиям во многом удовлетворяет метод каскадного кодирования, обеспечивающий необходимый компромисс между исправляющей способностью и сложностью декодера. Каскадные коды используются в практике передачи дискретных сигналов в качестве методов реализации кодов большой длины и высокой корректирующей способности. Эта цель может быть достигнута применением нескольких ступеней кодирования; наибольшее распространение получили две ступени кодирования различными кодами, например по схеме, показанной на рисунке 6.1. Вторая ступень кодирования в последовательном каскадном кодеке формирует k2 строк, каждая из которых состоит из k1 информационных символов кода (n1, k1) 1-ой ступени (внутреннего кода). Рисунок 6.34 – Последовательное каскадное кодирование В каскадном коде каждая последовательность из k1 двоичных символов внутреннего кода представляется как один символ недвоичного кода (основа­ние этого кода равно q=2k1) 2-ой ступени (внешнего кода); к k2 информационным символам внешнего кода приписывается (n2-k2) проверочных символов, каждый из которых также состоит из k1 двоичных символов; в результате образуется кодовое слово внешнего кода (n2, k2). Затем каждая строка из k1 двоичных символов кодируется кодом (n1, k1) и к каждой строке приписывается (n1- k1) проверочных символов кода 1-ой ступени (внутреннего кода). При этом следует иметь в виду, что кодовое слово кода 1-ой ступени может составлять только часть символа кода 2-ой ступени, тогда основание этого кода будет равно q=2b∙k1, где b- целое число. В другом методе формирования каскадного кода (иногда называемого итеративным кодом) k2 информационных блоков, каждый из которых состоит из k1 двоичных символов кода 1-ой ступени (внутреннего кода) записываются в виде строк матрицы; каждый ее столбец образует k2 символов, которые являются информационными символами кода (n2, k2) 2-ой ступени (внешнего кода). Затем, как и при каскадном кодировании, каждая строка из k1 двоичных символов кодируется кодом (n1, k1) и к каждой строке приписывается (n1-k1) проверочных символов кода 1-ой ступени (внутреннего кода). В результате и в том и другом случае образуется блок двоичных символов (матрица n1n2) длиной n1n2, содержащий k1k2 информационных символов, а общее кодовое расстояние равно произведению кодовых расстояний внешнего и внутреннего кодов (6.111) где aij  информационные символы, bij  проверочные символы. Хотя общая длина кода равна n1 n2, декодирование может производиться с помощью двух декодеров для кодов с длинами n1 и n2 соответственно, что позволяет уменьшить сложность декодирования по сравнению с той, которая потребовалась бы при использовании одной ступени декодирования. В качестве кодов 1-ой и 2-ой ступеней могут использоваться как блочные, так и сверточные коды. При этом на первой ступени целесообразно применить такой код, который обеспечивает уменьшение вероятности ошибки при возможно меньшем отношении сигнал/шум в канале связи. Это могут быть ортогональные (или биортогональные) коды при q=2k1-ичной модуляции, короткие блочные или сверточные коды. В качестве внешнего кода могут применяться как блочные (например, циклические), так и сверточные коды. Одним из кодов 2-ой ступени (внешним кодом) часто используются недвоичные циклические коды Рида-Соломона (коды РС), которые являются кодами с максимальным кодовым расстоянием d=n2–k2+1. Известна оценка вероятности ошибки на выходе декодера кодов РС в каналах с независимыми ошибками [2] (6.112) где t  кратность ошибок, исправляемых внешним кодом, p1  вероятность ошибки на выходе декодера 1-ой ступени,  множитель, учитывающий среднее число ошибок в двоичных символах на одну ошибку недвоичного символа кода РС. Каскадное кодирование с внешним кодом РС (или сверточным кодом с итерационным декодированием) и внутренним сверточным кодом R=1/2 (с декодером Витерби) позволяют работать в канале с отношением сигнал/шум 2,0 … 2,5 дБ, обеспечивая вероятность ошибки декодирования pд =10-5 . Необходимо также отметить, что для повышения качества декодирования при последовательном включении кодеров и декодеров полезно установить между кодерами перемежитель, а между декодерами деперемежитель. Это позволяет устранить влияние пакетирования ошибок после декодирования кодовых слов внутреннего кода (даже в каналах с независимыми ошибками) и улучшить режим работы внешнего декодера. 6.2 Параллельные каскадные коды Анализ характеристик последовательных каскадных кодов, рассмотренных выше, показал, что они на несколько децибел отстоят от границы Шеннона. Одна из причин снижения эффективности последовательных каскадных кодов – –кодирование внутренним кодером как информационных, так и проверочных битов внешнего кодера. Таким образом, часть пропускной способности канала тратится на передачу символов, являющихся "проверочными от проверочных". Работы по совершенствованию методов исправления ошибок с помощью каскадного кодирования привели к разработке группой французских ученых во главе с К. Берру сравнительно нового класса кодов — параллельных каскадных кодов с итерационным декодированием, обычно называемых турбокодами [16]. Параллельное каскадирование исключает передачу двойных проверочных символов, вследствие чего исправляющая способность возрастает. Применение схем турбокодирования позволяет получить результаты, более близкие к границе Шеннона (проигрыш около 0,27...0,5 дБ), по крайней мере, при использовании глубокого перемежения и при вероятности ошибки по битам около 10-5. Проведенные исследования показали, что с помощью турбокодов можно достигнуть вероятности ошибки декодирования, равной 10-5 при отношении сигнал/шум E/N0 = 0,7 дБ (E- энергия сигнала, N0 – спектральная плотность шума), но при этом потребуется большая длина блока кодируемых данных, равная 65532 символов [17]. Турбокод может рассматриваться как блочный код с очень большой длиной блока. В компонентных кодерах турбокодека могут использоваться коды Хемминга, БЧХ, Рида-Соломона и сверточные, работающие в блочном режиме [8,15]. Турбокод образуется при параллельном каскадировании двух или более систематических кодов. Обычно используются два или три первичных (компонентных) кода, а соответствующие им турбокоды называются двумерными или трехмерными. Напомним, что у кодеров систематических кодов один из выходов повторяет входную последовательность данных, а на другом формируется последовательность проверочных символов. Обобщенная структурная схема турбокодера показана на рисунке 6.2. Блок данных u длиной k символов поступает сначала на вход турбокодера. Последовательность символов x0= u поступает на систематический выход турбокодера и параллельно на М ветвей, состоящих из последовательно включенных перемежителя и компонентного кодера. Рисунок 6.35 – Структурная схема турбокодера В этой схеме передаваемая информация совместно используется во всех компонентных кодерах. Каждый перемежитель преобразует структуру последовательности символов x0 по псевдослучайному закону и выдает пакет на вход соответствующего кодера. Возможность исправления ошибок зависят не только от минимального кодового расстояния, но и от распределения весов кода, в частности, от числа кодовых слов с низким весом. Поэтому задачей перемежителя является преобразование входной последовательности таким образом, чтобы последовательности, приводящие к кодовым словам с низким весом на выходе первого компонентного кодера, были преобразованы в другие, порождающие различные кодовые слова с высоким весом на выходах остальных кодеров. Следовательно, компонентные кодеры реагируют на блок входных данных формированием различных кодовых слов с различным весом. Псевдослучайные перемежители обеспечивают в этом смысле оптимальные результаты [2]. На выходах компонентных кодеров каждой из М ветвей образуются последовательности проверочных символов x1... xM. Поскольку информационные последовательности (систематическая часть) на выходах кодеров всех ветвей идентичны с точностью до линейной операции перемежения, в канал передается только одна из них, что существенно повышает скорость передачи и эффективность системы кодирования. Эта информационная последовательность x0 мультиплексируется с проверочными последовательностями x1... xM, образуя кодовое слово, которое подлежит передаче по каналу. Скорость кода на выходе турбокодера R = 1/(М+ 1). Для повышения скорости кода применяют выкалывание (перфорацию) определенных проверочных символов выходной последовательности кодера. В типичном случае после выкалывания в канал передается только половина проверочных символов каждой ветви. Тогда скорость кода возрастает до R =1/(М/2+1). В большинстве случаев ограничиваются использованием двух ветвей кодирования (М = 2) без перемежителя в первой ветви (рисунок 6.3). Тогда операция выкалывания сводится к передаче в канал нечетных проверочных символов первого кодера и четных проверочных символов второго. В совокупности с информационной последовательностью это приводит к результирующей кодовой скорости R = 1/2. Выкалывание позволяет устанавливать произвольное значение кодовой скорости и даже адаптировать параметры кодера к свойствам канала. Если в канале возрастает уровень шумов, то уменьшение степени выкалывания вносит в кодированный поток дополнительную избыточность и повышает исправляющую способность кода. Рисунок 6.36 – Схема турбокодера с двумя одинаковыми рекурсивными кодерами На рисунке 6.3 показана схема турбокодера, в котором кодирующее устройство состоит из двух двоичных сверточных кодеров (скорость R =1/2). Между кодерами расположен N-символьный перемежитель. Без выкалывания скорость кода равна 1/3, то есть N информационных символов содержится в блоке из 3N символов на выходе кодека. Кодеры могут быть построены по схеме классического сверточного кодера. Однако для каскадирования вместо обычного последовательного включения кодеров применяется параллельная схема их взаимосвязи. Заметим также, что сверточные кодирующие устройства часто строятся по рекурсивной схеме. Известно, что нерекурсивный сверточный кодер эквивалентен рекурсивному систематическому кодеру в смысле свойств набора кодовых слов; однако, что для рекурсивного кодирующего устройства, кодированная последовательность будет иметь конечный вес только тогда, когда входная последовательность делится на g1(x). Это обстоятельство может быть использовано для упрощения декодирования по алгоритму Витерби. В качестве примера возможного варианта практической реализации турбокодера со скоростью 1/2 рассмотрим структурную схему, показанную на рисунке 6.3. В схеме имеются два идентичных систематических рекурсивных сверточных кодера (рисунок 6.4), в каждом из которых имеется четырехразрядный регистр сдвига с логическими связями через сумматоры по модулю 2. Матрица производящих полиномов для нерекурсивного сверточного кода R =1/2 имеет вид Gнр = [g1(x), g2(x)]; эквивалентный рекурсивный систематический кодер имеет матрицу производящих полиномов вида Gр =. (6.113) Рисунок 6.37 – Рекурсивный систематический кодер В основе декодирования кодов, исправляющих ошибки, лежит сравнение вероятностных характеристик различных кодовых слов, а применительно к сверточным кодам с декодированием по алгоритму Витерби— различных путей на решетчатой диаграмме. Если имеется некоторое предварительное знание о принимаемом сигнале до его декодирования, то такая информация называется априорной и ей соответствует априорная вероятность. В противном случае имеет место только апостериорная информация. При декодировании турбокодов существенным является использование обоих видов информации. Классический турбодекодер, соответствующий турбокодеру с М компонентными кодерами, содержит М компонентных декодеров, каждый из которых использует алгоритм МАВ. Рассмотрим процесс декодирования для случая, когда кодирование осуществляется двухкомпонентным турбокодером. При этом в результате демультиплексирования на входе декодера имеется информационная y0 и две кодированные проверочные последовательности y1 и y2. После декодирования информационной и первой проверочной последовательностей получается начальная оценка информационной последовательности, которая может использоваться как априорная информация при декодировании второй проверочной последовательности во втором компонентном декодере. Такой подход. требует, чтобы компонентный декодер мог использовать мягкое решение для входных данных ("мягкий" вход) и выдавать данные в непрерывном диапазоне амплитуд или, по крайней мере, без грубого квантования ("мягкий" выход). В соответствии с этим алгоритмом схема декодера для первого шага декодирования имеет структуру, показанную на рисунке 6.5. Рисунок 6.38 – Структурная схема турбодекодера В работе [16] для декодирования турбокодов был предложен алгоритм максимума апостериорной вероятности (МАВ), часто называемый также алгоритмом BCJR (по фамилия авторов – Bahl, Cocke, Jelinek и Raviv]. Алгоритм BCJR отличается от алгоритма Витерби "мягкой" структурой сигнала оценки декодируемого символа, при которой уровень выходного сигнала соответствует степени доверия вынесенного решения. Если декодер Витерби в результате оценки максимального правдоподобия минимизирует ошибку в декодируемом кодовом слове (находит наиболее вероятную информационную последовательность), то алгоритм BCJR минимизирует ошибку в символах (находит наиболее вероятное значение информационного символа), вычисляя апостериорные вероятности при декодировании каждого информационного символа в кодовом слове. Характеристики исправляющей способности при использовании алгоритмов Витерби и BCJR в области высоких значений отношения сигнал/шум отличается достаточно мало, но при низких значениях отношения сигнал/шум алгоритм BCJR превосходит алгоритм Витерби. Недостатком алгоритма BCJR является повышенная вычислительная сложность по сравнению с алгоритмом Витерби. Поэтому в дальнейшем был разработан модифицированный алгоритм Витерби с "мягким" выходом, известный как алгоритм SOVA (Soft-Output Viterbi Algorithm). Алгоритм SOVA относится к классу алгоритмов "мягкий вход, мягкий выход" (SISO), и его реализация примерно вдвое сложнее алгоритма Витерби. Поэтому характерная особенность алгоритма SOVA — использование априорной информации на входе декодера и выдача апостериорной информации на его выходе. Алгоритм SOVA может применяться в качестве компонентных декодеров как при последовательном, так и при параллельном каскадировании. Качество декодирования турбокодов, как и других кодов, можно существенно улучшить при проведении нескольких итераций декодирования одного и того же блока информации с последовательной обработкой в нескольких физических декодерах. Однако оптимальные результаты получаются в схеме с обратной связью – с выхода турбодекодера на его вход. В итеративном турбодекодере, как и в итерационном пороговом декодере (ИПД), после очередной итерации "мягкие" выходные сигналы каждого элементарного декодера подаются на другие аналогичные декодеры для уточнения выносимого решения. Предположим, что два информационных символа в турбодекодере связаны некоторыми проверочными уравнениями. Тогда для их суммы можно записать следующее логическое проверочное выражение: xp = x01 + x02. Если оба члена xp и x02 декодированы с высокой надежностью, то и для x01 может быть получена весьма надежная оценка. Если же оценка x02 имеет низкую надежность, то нельзя улучшить надежность x01. В итерационном турбодекодере после декодирования первой последовательности значения x01 и x02 могут иметь невысокую надежность, но x02 связан проверочными соотношениями с очень надежными символами во второй кодированной последовательности. Это значит, что можно провести вторую итерацию декодирования и при вычислении проверок в первой кодированной последовательности результатов учесть более надежную оценку x02. Этот процесс может быть продолжен в течение нескольких итераций, пока обеспечивается прирост надежности декодируемых символов. Итерационный декодер, использующий алгоритм BCJR и МАВ декодеры показан на рисунке 6.6. Рисунок 6.39 – Схема итерационного турбодекодера на основе алгоритма BCJR Обратите внимание как включены перемежители и деперемежитель для обеспечения параллелизма и взаимодействия при подаче дополнительной информация в виде последовательностей L12 и L21 на соответствующие входы каждого декодера. L12 и L21 являются мягкими выходами декодеров, определяемыми отношением правдоподобия в каждом из них. Необходимое число итераций 1015. Результаты декодирования могут быть взяты с выхода любого декодера. Вероятность ошибки декодирования для турбокодеков в каналах с гауссовским шумом для сверточных кодов , (6.114) где d – свободное расстояние кода; nw – множество кодовых слов веса w; wd – средний вес информационных последовательностей в кодовых словах; na – кодовое ограничение; E/N0 – отношение сигнал/шум; F(z)= – интеграл вероятностей. Как видно из выражения (6.4) вероятность ошибки декодирования можно уменьшить, увеличивая длину перемежителя N. Поэтому в практических приложениях длина перемежителя обычно достигает тысячи и десятки тысяч символов. Анализ показывает, что при E/N0 выше средних значений вероятность ошибок декодирования асимптотически стремится к значению , (6.115) где , – максимальный вес и соответствующее множество. Поскольку расстояние d в общем случае относительно мало, то снижение вероятности ошибки ниже 10-5 ведет к достаточно плоскому ходу асимптоты (6.5). На рисунке 6.7 в качестве примера показаны кривые зависимости вероятностей ошибки декодирования, полученные моделированием на эвм турбодекодера сверточного кода Gр =, и асимптоты, построенные в соответствии с формулой (6.5). Рисунок 6.40 – Вероятность ошибки декодирования для турбокода R=1/2 (31,33) Перемежитель 2 отличается от перемежителя 1 тем, что при его построении были приняты меры по улучшению спектра весов кодовых последовательностей на выходе перемежителя. Увеличение глубины перемежения N способствует снижению уровня асимптоты. В области малых и средних значений отношения сигнал/шум применение схем турбокодирования позволяет получить результаты, приближающиеся к границе Шеннона, по крайней мере, при вероятности ошибки декодирования около 10-5. Но для вероятностей ошибки ниже 10-7, что требуется во многих прикладных задачах передачи данных и цифрового ТВ вещания, турбокодирование в классическом виде неприменимо. Для преодоления указанного недостатка используют сочетание последовательного каскадного и турбокодирования. В такой комбинированной схеме в качестве внутреннего используется турбокод, а в качестве внешнего – блочный, например, БЧХ или Рида-Соломона. Поскольку при последовательном каскадировании очень хорошие результаты получаются в области больших, а при параллельном – в области малых и средних значений отношения сигнал/шум, результирующая характеристика комбинированного кодека обеспечивает существенный выигрыш во всем рабочем диапазоне. Возможен вариант построения параллельного каскадного кода на основе сверточных кодов с ортогональными проверками и итерационным пороговым декодированием. При этом структурные схемы кодера и декодера не отличаются от показанных на рисунках 6.2 и 6.5, а в качестве компонентных декодеров используются блочные итерационные декодеры с переменным уровнем порога. Объем псевдослучайного перемежителя и деперемежителя (ПРМ и ДПРМ) в канале с независимыми ошибками не превышает 10÷15 кодовых блоков. В свою очередь число двоичных символов в кодовом блоке должно быть больше максимальной степени производящего полинома, умноженного на число информационных символов в кадре k0 при данной скорости кода R= k0/n0. (длина кодового слова [k0·maxdeg(g(x))+1]). Дальнейшее увеличение объема перемежителя не приводит к существенному улучшению качества декодирования. На рисунке 6.8 приведены результаты статистических испытаний имитационных моделей предлагаемых кодов с R=1/х в сравнении с обычным сверточным кодом такой же скорости и аналогичным алгоритмом декодирования. Использованы сверточные самоортогональные коды R=1/2 (406,203) и (94,47), R=2/3 (609,406) с производящими полиномами G1=(1, 1+x7 +x27 +x76 +x113 +x137 +x155 +x156+x170 +x202 ), G2=(1, 1+x5 +x20+x46), G3=(1, 1+x12 +x25 +x28 +x78 +x83 +x100 +x109 +x145+x199, 1+x7 +x27 +x76 +x113 +x137 +x155 +x156+x170 +x202 ). По результатам испытаний можно предположить, что существенный выигрыш в помехоустойчивости параллельных кодеков в сравнении с обычным сверточным кодеком с декодером АИПД достигается за счет уменьшения влияния пакетирования ошибок на выходе декодера 1, благодаря чему декодер 2 также работает в условиях независимых ошибок. Можно также заметить, что начало выигрыша в помехоустойчивости определяется пороговыми свойствами декодера 1, то есть вероятностью PП ошибок в канале, выше которой декодер 1 начинает размножать ошибки. Кривая 3 получена с первым декодером R=2/3, имеющим более высокое значение PП в сравнении с декодерами R=1/2 (кривые 5 и 6). В декодере (кривая 7) декодер 1 имеет только 4 проверки и соответственно меньшее значение PП. Однако этот декодер уступает по корректирующей способности первому декодеру (кривая 5) и, соответственно, кривая 7 в последующем становится более пологой. 1-без кодирования, ФМ, когерентный прием; 2-сверточный код R=1/2, декодер пороговый, 5 итераций; 3-турбокод R=1/2 на основе сверточного кода R=2/3, декодеры пороговые, 5 итераций; 4-сверточный код R=1/3, декодер пороговый, 5 итераций; 5-турбокод R=1/3 на основе сверточного кода R=1/2, декодеры пороговые, 5 итераций; 6-турбокод R=1/2,5 на основе сверточных кодов R=1/2 и R=2/3, декодеры пороговые, 5 итераций; 7-турбокод R=1/3 на основе св. кодов R=1/2 (94.47 ) и (406,203), декодеры пороговые, 5 итераций; 8-последовательный каскадный код R=1/3 на основе сверточных кодов R=1/2 (400,200 ) и (406,203), декодеры пороговые 5 итераций с перемежителем Рисунок 6.41 – Зависимость вероятности ошибки декодирования от отношения сигнал/шум в канале с гауссовским шумом Полученные результаты в отличие турбокодеков на основе сверточных кодов малой длины с декодированием по модифицированному алгоритму Витерби или алгоритму МАВ (рисунок 6.8) обеспечивают высокий выигрыш в помехоустойчивости при средних и больших отношениях сигнал/шум. Однако имеются основания полагать [2], что при использовании в декодерах мягких решений кривые представленные на рисунке 6.8 сдвинутся вправо на 0,2÷0,3 дБ. Кроме того, реализация пороговых декодеров существенно проще (по оценке [3] на два порядка по числу операций), так как сложность декодирования АИПД растет только пропорционально длине блока декодирования и числу проверок J. Вероятность ошибок декодирования при увеличении отношения сигнал/шум также асимптотически стремится к некоторому значению, которое определяется числом проверок в последнем декодере. Уравнение этой асимптоты может быть записано в виде (6.116) где J0=J для кодов R=k0 /n0, k0 >1 и J0=( n0 -1)J для кодов k0 =1. Следует заметить, что эти асимптоты проходят гораздо ниже и круче по сравнению с показанными на рисунке 6.8 при одинаковой скорости кодов. На рисунке 6.8 (кривая 8) приведены результаты применения в том же канале последовательного каскадного кодека с перемежителем между каскадами. Его следует сравнивать с кодеками той же скорости (кривые 4 и 5). Этот кодек уступает параллельному каскадному кодеку (кривая 5) в области малых отношений сигнал/шум, но имеет заметный выигрыш в области больших значений отношения сигнал/шум. Это объясняется тем, что при параллельном каскадировании в меньшей степени проявляется эффект размножения ошибок, а в области больших отношений сигнал/шум декодеры второй и более ступеней используют проверочные символы без исправления ошибок, в отличие от последовательного каскадирования, где ошибки исправляются и в проверочных символах. ПРИЛОЖЕНИЕ А П А.1 Таблица производящих полиномов циклических кодов Ниже приводится таблица полиномов циклических кодов в восьмеричной записи, которая составлена на основе аналогичной таблицы в [2] и содержит ряд дополнительных позиций. В этой таблице: № – номер полинома в таблице; t – максимальная кратность исправляемых ошибок; (n,k) – число символов в кодовом слове и его информационная часть; g(x) – полином в восьмеричной записи. _№_t_(n,k)_g(x)_____________________________________________________ 1 : 1: (7,4) '13', 2 : 3: (7,1) '177', 3 : 1: (15,11) '23', 4 : 2: (15,7) '721', 5 : 3: (15,5) '2467', 6 : 7: (15,1) '77777', 7 : 1: (31,26) '45', 8 : 2: (31,21) '3551', 9 : 3: (31,16) '107657', 10 : 5: (31,11) '5423325', 11 : 7: (31,6) '313365047', 12 :15: (31,1) '17777777777', 13 : 1: (63,57) '103', 14 : 2: (63,51) '12471', 15 : 3: (63,45) '1701317', 16 : 4: (63,39) '166623567', 17 : 5: (63,36) '1033500423', 18 : 6: (63,30) '157464165547', 19 : 7: (63,24) '17323260404441', 20 :10: (63,18) '1363026512351725', 21 :11: (63,16) '6331141367235453', 22 :13: (63,10) '472622305527250155', 23 :15: (63,7) '5231045543503271737', 24 :31: (63,1) '777777777777777777777', 25 : 1: (127,120) '211', 26 : 2: (127,113) '41567', 27 : 3: (127,106) '11554743', 28 : 4: (127,99) '3447023271', 29 : 5: (127,92) '624730022327', 30 : 6: (127,85) '130704476322273', 31 : 7: (127,78) '26230002166130115', 32 : 9: (127,71) '6255010713253127753', 33 :10: (127,64) '1206534025570773100045', 34 : 1: (255,247) '435', 35 : 2: (255,239) '267543', 36 : 3: (255,231) '156720665', 37 : 4: (255,223) '75626641375', 38 : 5: (255,215) '23157564726421', 39 : 6: (255,207) '16176560567636227', 40 : 7: (255,199) '7633031270420722341', 41 : 8: (255,191) '2663470176115333714567', 42 : 9: (255,187) '52755313540001322236351', 43 :10: (255,179) '22624710717340432416300455', 44 :11: (255,171) '15416214212342356077061630637', 45 :12: (255,163) '7500415510075602551574724514601', 46 :13: (255,155) '3757513005407665015722506464677633', 47 :14: (255,147) '1642130173537165525304165305441011711', 48 :15: (255,139) '461401732060175561570722730247453567445', 49 :18: (255,131) '215713331471510151261250277442142024165471', 50 :19: (255,123) '120614052242066003717210326516141226272506267', 51 :21: (255,115) '60526665572100247263636404600276352556313472737', 52 :22: (255,107) '22205772322066256312417300235347420176574750154441', 53 :23: (255,99) '10656667253473174222741416201574332252411076432303431', 54 :25: (255,91) '6750265030327444172723631724732511075550762720724344561', 55 :26: (255,87) '110136763414743236435231634307172046206722545273311721317', 56 :27: (255,79) '66700035637657500020270344207366174621015326711766541342355', 57 :29: (255,71) '24024710520644321515554172112331163205444250362557643221706035', 58 :30: (255,63) '10754475055163544325315217357707003666111726455267613656702543301', 59 :31: (255,55) '7315425203501100133015275306032054325414326755010557044426035473617', 60 :42: (255,47) '2533542017062646563033041377406233175123334145446045005066024552543173', 61 :43: (255,45) '15202056055234161131101346376423701563670024470762373033202157025051541', 62 :45: (255,37) '5136330255067007414177447245437530420735706174323432347644354737403044003', 63 :47: (255,29) '3025715536673071465527064012361377115342242324201174114060254657410403565037', 64 :55: (255,21) '1256215257060332656001773153607612103227341405653074542521153121614466513473725', 65 :59: (255,13) '464173200505256454442657371425006600433067744547656140317467721357026134460500547', 66 :63: (255,9) '15726025217472463201031043255355134614162367212044074545112766115547705561677516057', 67 :127: (255,1) '7777777777777777777777777777777777777777777777777777777777777777777777777777777777777' 68 : 4: ( 73,45) '2220210525', [мажоритарный код] 69 : 4: ( 41,21) '6647133', [непримитивные коды БЧХ] 70 : 4: ( 73,46) '1717773537', 71 : 4: ( 65,40) '354303067', 72 : 2: ( 65,63) '10761', 73 : 5: ( 47,24) '42073357', 74 : 2: ( 33,22) '5145', 75 : 2: ( 21,12) '1663', 76 : 2: ( 17,9) '727', 77 : 3: ( 23,12) '5343', 78 : 1: ( 7,3 ) '35'. ПРИЛОЖЕНИЕ Б Таблица производящих полиномов сверточных кодов Номер Степени полиномов g(x) н-на J - число проверок, nr = max[deg g(x)] _№_J_nr__степени g(x) { 1 : 2: 1 } (0,1) { 2 : 2: 2 } (0,2) { 3 : 2: 3 } (0,3) { 4 : 2: 4 } (0,4) { 5 : 3: 3 } (0,2,3) { 6 : 3: 5 } (0,3,5) { 7 : 3: 7 } (0,1,7) { 8 : 3: 7 } (0,3,7) { 9 : 3: 8 } (0,1,8) { 10: 3: 8 } (0,2,8) { 11: 3: 8 } (0,3,8) { 12: 3: 8 } (0,6,8) { 13: 3: 9 } (0,2,9) { 14: 3: 10} (0,4,10) { 15: 3: 10} (0,1,10) { 16: 3: 11} (0,5,11) { 17: 3: 11} (0,6,11) { 18: 3: 12} (0,1,12) { 19: 3: 12} (0,11,12) { 20: 3: 12} (0,3,9) { 21: 3: 14} (0,10,14) { 22: 3: 15} (0,1,15) { 23: 3: 15} (0,2,15) { 24: 3: 17} (0,4,17) { 25: 3: 17} (0,7,17) { 26: 3: 18} (0,4,18) { 27: 3: 18} (0,10,18) { 28: 3: 19} (0,3,19) { 29: 3: 20} (0,15,20) { 30: 3: 22} (0,13,22) { 31: 4: 6 } (0,2,5,6) { 32: 4: 12} (0,8,9,12) { 33: 4: 13} (0,6,11,13) { 34: 4: 18} (0,8,17,18) { 35: 4: 19} (0,3,15,19) { 36: 4: 21} (0,16,20,21) { 37: 4: 24} (0,11,18,24) { 38: 4: 25} (0,2,10,25) { 39: 4: 25} (0,4,12,25) { 40: 4: 26} (0,14,17,26) { 41: 4: 27} (0,7,9,27) { 42: 4: 28} (0,5,11,28) { 43: 4: 31} (0,1,15,31) { 44: 4: 31} (0,3,19,31) { 45: 4: 32} (0,23,25,32) { 46: 4: 32} (0,2,8,32) { 47: 4: 32} (0,10,29,32) { 48: 4: 36} (0,1,15,36) { 49: 4: 37} (0,25,36,37) { 50: 4: 38} (0,20,30,38) { 51: 4: 39} (0,22,26,39) { 52: 4: 40} (0,29,34,40) { 53: 4: 42} (0,3,19,42) { 54: 4: 43} (0,21,34,43) { 55: 4: 43} (0,4,20,43) { 56: 4: 45} (0,7,17,45) { 57: 4: 46} (0,3,19,46) { 58: 4: 46} (0,5,20,46) { 59: 4: 47} (0,29,33,47) { 60: 4: 66} (0,15,29,66) { 61: 4: 89} (0,1,3,89) { 62: 4: 103} (0,68,98,103) { 63: 4: 107} (0,82,100,107) { 64: 4: 124} (0,49,60,124) { 65: 4: 126} (0,55,79,126) { 66: 4: 141} (0,22,83,141) { 67: 4: 147} (0,19,99,147) { 68: 4: 156} (0,50,144,156) { 69: 5: 11} (0,2,7,10,11) { 70: 5: 18} (0,4,10,15,18) { 71: 5: 22} (0,2,9,21,22) { 72: 5: 25} (0,15,19,21,25) { 73: 5: 26} (0,3,13,24,26) { 74: 5: 34} (0,7,25,26,34) { 75: 5: 40} (0,8,17,39,40) { 76: 5: 41} (0,3,13,36,41) { 77: 5: 45} (0,30,35,41,45) { 78: 5: 46} (0,18,25,44,46) { 79: 5: 50} (0,14,34,47,50) { 80: 5: 53} (0,24,46,50,53) { 81: 5: 53} (0,25,27,46,53) { 82: 5: 67} (0,27,56,61,67) { 83: 5: 71} (0,12,45,63,71) { 84: 5: 71} (0,20,30,38,71) { 85: 5: 73} (0,1,15,36,73) { 86: 5: 75} (0,43,66,68,75) { 87: 5: 76} (0,45,48,64,76) { 88: 5: 78} (0,3,19,52,78) { 89: 5: 82} (0,21,25,39,82) { 90: 5: 83} (0,38,48,55,83) { 91: 5: 84} (0,5,20,47,84) { 92: 5: 85} (0,11,12,62,85) { 93: 5: 88} (0,2,8,32,88) { 94: 5: 89} (0,36,67,76,89) { 95: 5: 95} (0,30,35,84,95) { 96: 5: 113} (0,16,39,72,113) { 97: 5: 140} (0,1,3,30,140) { 98: 5: 142} (0,35,59,109,142) { 99: 5: 145} (0,22,83,141,145) {100: 5: 147} (0,53,66,128,147) {101: 6: 17} (0,2,7,13,16,17) {102: 6: 38} (0,8,27,28,32,38) {103: 6: 39} (0,14,21,23,36,39) {104: 6: 50} (0,15,22,23,40,50) {105: 6: 58} (0,3,5,14,34,58) {106: 6: 61} (0,12,16,42,48,61) {107: 6: 71} (0,5,26,51,55,71) {108: 6: 72} (0,6,7,41,60,72) {109: 6: 77} (0,10,32,47,49,77) {110: 6: 82} (0,8,11,24,44,82) {111: 6: 96} (0,46,54,80,83,96) {112 : 6:100} (0,6,47,64,65,100) {113: 6:101} (0,38,40,62,71,101) {114: 6:103} (0,10,14,21,88,103) {115: 6:104} (0,5,28,48,60,104) {116: 6:118} (0,42,87,90,106,118) {117: 6:120} (0,1,15,36,73,120) {118: 6:122} (0,55,82,111,116,122) {119: 6:123} (0,20,30,38,71,123) {120: 6:124} (0,49,92,115,117,124) {121: 6:125} (0,62,86,98,102,125) {122: 6:126} (0,21,25,39,82,126) {123: 6:130} (0,41,77,108,117,130) {124: 6:131} (0,11,12,62,85,131) {125: 6:141} (0,58,96,106,113,141) {126: 6:142} (0,2,8,32,88,142) {127: 6:144} (0,5,20,47,84,144) {128: 6:146} (0,3,19,52,78,146) {129: 6: 181} (0,13,23,37,71,181) {130: 6: 238} (0,64,75,102,196,238) {131: 6: 305} (0,2,61,69,289,305) {132: 6: 339} (0,41,221,257,311,339) {133: 6: 395} (0,45,191,247,310,395) {134: 6: 396} (0,208,280,284,377,396) {135: 6: 399} (0,84,162,266,316,399) {136: 7: 25} (0,2,7,15,21,24,25) {137: 7: 46} (0,1,28,31,44,46) {138: 7: 54} (0,7,17,29,40,49,54) {139: 7: 69} (0,12,17,45,48,68,69) {140: 7: 90} (0,6,10,32,40,47,90) {141: 7: 91} (0,13,27,29,38,73,91) {142: 7:106} (0,4,39,68,80,90,106) {143: 7:110} (0,14,60,61,66,91,110) {144: 7:116} (0,13,34,37,45,107,116) {145: 7:122} (0,2,17,59,95,115,122) {146: 7: 178} (0,38,44,84,125,147,178) {147: 7: 237} (0,95,173,183,187,207,237) {148: 7: 324} (0,38,44,84,125,147,178) {149: 7: 437} (0,197,271,310,409,426,437) {150: 7: 451} (0,48,118,161,228,436,451) {151: 7: 467} (0,21,181,243,363,392,467) {152: 7: 490} (0,186,231,300,336,433,490) {153: 8: 35} (0,7,10,16,18,30,31,35) {154: 8: 77} (0,27,39,47,61,64,70,77) {155: 8: 78} (0,19,21,45,63,73,74,78) {156: 8:100} (0,28,35,47,58,71,80,100) {157: 8:124} (0,16,31,34,48,75,85,124) {158: 8:127} (0,21,25,26,81,87,89,127) {159: 8:141} (0,19,59,68,85,88,103,141) {160: 8:162} (0,39,87,117,138,148,154,162) {161: 8:172} (0,2,13,25,96,118,168,172) {162: 8:178} (0,7,65,70,97,98,144,178) {163: 8: 289} (0,56,130,237,238,240,274,289) {164: 8: 376} (0,9,32,50,103,207,215,376) {165: 8: 458} (0,31,99,111,166,195,235,458) {166: 8: 473} (0,208,251,297,310,336,357,473) {167: 8: 575} (0,38,152,156,373,383,455,575) {168: 8: 592} (0,113,194,281,309,407,557,592) {169: 8: 609} (0,57,244,323,334,456,548,609) {170: 9: 45} (0,3,9,16,20,21,35,43,45) {171: 9: 97} (0,16,37,44,47,70,82,83,97) {172: 9:102} (0,22,24,30,41,73,93,98,102) {173: 9:156} (0,26,58,102,109,125,150,155,156) {174: 9:160} (0,12,29,39,72,91,146,157,160) {175: 9:164} (0,38,56,78,80,115,143,151,164) {176:10: 55} (0,2,14,21,29,32,45,49,54,55) {177:10:116} (0,23,39,57,60,74,101,103,112,116) {178:10:130} (0,1,6,25,32,72,100,108,120,130) {179:10:152} (0,8,38,48,59,82,111,146,150,152) {180:10:199} (0,12,25,28,78,83,100,109,145,199) {181:10:202} (0,7,27,76,113,137,155,156,170,202) {182:11: 72} (0,3,14,16,20,41,48,53,63,71,72) {183:11:167} (0,5,12,53,72,81,135,136,146,159,167) {184:11:168} (0,17,46,50,52,66,88,125,150,165,168) {185:12: 85} (0,2,6,24,29,40,43,55,68,75,76,85) {186:12:193} (0,26,34,47,57,58,112,121,140,181,188,193) {187:12:195} (0,17,46,50,52,66,88,125,150,165,168,195) {188:13:114} (0,23,28,29,37,53,63,75,94,96,107,111,114) {189:13:240} (0,16,64,104,122,124,146,159,167,171,178,237,240) {190:13:250} (0,30,39,53,68,129,139,165,170,216,222,249,250) {191:14:127} (0,5,28,38,41,49,50,68,75,92,107,121,123,127) {192:14:155} (0,2,3,10,26,39,43,61,109,121,130,136,141,155) {193:14:279} (0,2,7,42,45,117,163,185,195,216,229,246,255,279) {194:14:288} (0,8,12,27,28,64,113,131,154,160,208,219,233,288) {195:15:155} (0,4,5,15,33,57,59,78,105,117,125,139,142,148,155) {196:15:334} (0,45,59,86,103,179,202,230,245,263,267,279,298,309,334) {197:15:336} (0,13,60,70,108,110,162,182,183,188,191,273,297,329,336) {198:16:179} (0,6,19,40,58,67,78,83,109,132,133,162,165,169,177,179) {199:17:201} (0,18,24,46,50,67,103,112,115,126,128,159,166,167,186,196,201) {200:17:255} (0,1,3,7,15,31,63,90,116,127,136,181,194,204,233,238,255) {201:18:216} (0,2,10,22,53,56,82,83,89,98,130,148,153,167,188,192,205,216) {202:18:299} (0,1,3,30,37,50,55,76,98,117,129,133,157,189,199,222,293,299) {203:19:246} (0,1,6,25,32,72,100,108,120,130,153,169,187,190,204,231,233, 242,246) {204:20:283} (0,24,30,43,55,71,75,89,104,125,127,162,167,189,206,215,272, 275,282,283) {205:20:369} (0,1,19,28,96,118,151,153,176,202,240,254,290,296,300,307,337,361,366,369) {206:21:333} (0,4,23,37,40,48,68,78,138,147,154,189,204,238,250,251,256, 277,309,331,333) {207:22:359} (0,3,16,45,50,51,65,104,125,142,182,206,210,218,228,237,289,300,326,333,356,358) {208:23:372} (0,6,22,24,43,56,95,126,137,146,172,173,201,213,258,273,281,306,311,355,365,369,372) {209:24:425} (0,22,41,57,72,93,99,139,147,173,217,220,234,273,283,285,296,303,328,387,388, 392,416,425) БИБЛИОГРАФИЯ [1] Булгак В.В., Варакин Л.Е. и др. Концепция развития связи Российской Федерации. Серия «Технология Электронных Коммуникаций». Том 1. 1996.– 90c. [2] Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ./ Под ред. Б.С. Цыбакова.– М.: Радио и связь, 1987.– 392 с. [3] Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ./ Под ред. К.Ш. Зигангирова.– М.: Мир, 1986.– 576 с. [4] Теория передачи сигналов: Учебник для вузов/ А.Г.Зюко, Д.Д.Кловский, М.В.Назаров, Л.М.Финк.– М.: Радио и связь, 1986.– 304 с. [5] Макаров А.А., Чернецкий Г.А. Корректирующие коды в системах передачи информации: учеб. пособие / СибГУТИ, Новосибирск, 2000.– 101с. [6] Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ.– М.: Мир, 1976.– 594 с. [7] Корн Г., Корн Т. Справочник по матеметике для научных работников и инженеров.– М.: Наука, 1968.– 720 с. [8] Помехоустойчивость и эффективность систем передачи информации / А.Г.Зюко, А.И.Фалько, И.П.Панфилов, В.Л.Банкет, П.В.Иващенко / Под ред. А.Г.Зюко.– М.: Радио и связь, 1985.– 272 с. [9] Артемова О.А. Исследование эффективности помехоустойчивого кодирования при передаче данных сложными сигналами в телефонных каналах: Автореф. дис. ... канд.техн.наук.– Новосибирск, 1995.– 19с. [10] Месси Дж. Пороговое декодирование.– М: Мир, 1966г.– 208 c. [11] Брауде-Золотарев Ю.Н., Золотарев В.В. Оптимизация порогового декодирования // Труды НИИР, N 1, 1979.– C.40-45. [12] Robinson J.P., Bernstein A.J. A class of binary recurrent codes with limited error propagation // IEEE Trans. on Inf. Theory, IT-13, January 1967.– P.106-113. [13] Klieber E.J. Some difference triangles for constructing self orthogonal codes // IEEE Trans. on Inf. Theory, IT-16, March 1970.– P. 237-238. [14] Артемова О.А., Макаров А.А.. Устройство для порогового декодирования сверточных кодов.– Патент № 208153, H03 М13/12, 1997 г. [15] Berrou С., Glavieux А., Thitimasjshima Р. Near Shannon limit error correcting coding and decoding: Turbo codes (1) // Proc. IEEE Int. Conf. on Communications.– Geneva, Switzerland, Мау 1993.– Р.1064-1070. [16] Красносельский И.Н. Турбокоды: принципы и перспективы // Электросвязь №1, 2001.– C.17-20. [17] Макаров А.А., Ковязин В.И. Автоматизация проектирования систем передачи данных: Деп. в ЦНТИ “Информсвязь”, N 1997-св.94, 1994г. Свелана Владимировна Воробьева методы и устройства Помехоустойчивой радиосвязи конспект лекций Редактор: Корректор: ________________________________________________________________ Подписано в печать Формат бумаги 60х84/16, отпечатано на ризографе, шрифт 10, изд. л. 10,5, заказ № , тираж экз., ФГБОУ ВО «СибГУТИ», 630102, г. Новосибирск, ул. Кирова, 86