У. Питерсон - Коды, исправляющие ошибки (1267328), страница 89

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 89)

т. д. Ниже этот результат будет использован для того, чтобы показать, что для некоторых практически важных сверточных кодов размножения ошибок не происходит. Дальнейшие результаты по этому вопросу можно найти в работах !212, 258!. Информацию, поступающую по каналу обратной связи, можно не использовать, ли допустимо некоторое ухудшение характеристик декодера.

Очевидно,что без обратной связи не будет размножения ошибок. для несистематического кода ггри йо = 1 размножение ошибок происходит, если па субпорождающнх многочленов имеют общий нормированный сомножитель ненулевой степени. Это можно показать следующим образом. Пусть через й';(Р), ! = 1, 2, ..., пм обозначены субпорождающие многочлены; предположим, что а, (В) = а, (В) д,'. (В), ! = 1, 2, ..., где до(.0) — нормированный многочлен ненулевой степени.

Пусть передается нулевое слово, а па принятых многочленов г (В) д'(Р) при всех !. Но та же последовательность принимается и тогда, когда первоначальная информационная последовательность гп(0) = (1/до(В)). Так как 0" — 1 делится на дз(Т!) при некотором и, то т(б) †периодическ многочлен с периодом и. Таким образом„ в том илн ином случае комбинация ошибок ограниченной степени из равенства (13.2) приводит к размножению ошибок. !З.З. Коды, исправляющие одиночные и двойные ошибки Пример. В предыдущих примерах рассматривался (12, 9)-код, построенный указанным выше способом. В каждом из первых пс —— - 2 ' = 4 столбцов проверочной матрицы 1111 1010 1111 1100 1010 1111 н=~ за единицей следуют все четыре возможных набора длины 2.

При любом значении т можно построить двоичный сверточный код с параметрами па — — 2 ', йо=по — 1, г(=3 [334). Столбцы матрицы Вм т, е. первые пс столбцов матрицы Н, образуют приписыванием перед всеми 2 -' различными наборами длины т — 1 символа !. Расположение наборов длины т — 1 по столбцам несущественно; лишь для задания кода в систематическом виде нужно расположить нулевой набор длины и — 1 в столбце матрицы Н с номером ам который соответствует проверочному символу.

Определяемый такой матрицей (т2'"-', пг(2'" — ' — 1) )-код может исправлять все одиночные ошибки, так как никакие два из первых пз столбцов не совпадают и ни один из других столбцов, начинающихся с О, не совпадает нн с каким нз первых пз столбцов, начинающихся с 1. Лля получения других значений скорости эти коды, так же как блоковые, можно укорачивать. Этого можно добиться„приравнивая первые ! информационных символов нулю и исключая их из передачи. Распределение наборов длины и — 1 по столбцам матрицы ВЗ произвольно.

Однако если (т — 1)-мерный вектор является двоичной записью номера столбца, в котором он расположен, то декодирование может быть несколько упрощено. Нулевой набор длины т — 1 располагается в (проверочном) столбце с номером 2 -', Тогда первый символ синдрома будет 1, если имеется ошибка в нулевом блоке, и О в противном случае; другие т — 1 символов синдрома дают номер ошибочного символа, если имеет место ошибка.

Способ реализации процесса декодирования в этом случае достаточно ясен. После исправления одиночной ошибки синдром, который используется при декодировании следующего блока, должен быть изменен. Для рассматриваемого примера это просто значит, что синдром полагается равным нулю после исправления ошибки. Таким образом, согласно теореме 13.1, при декодировании не могут появляться дополнительные ошибки, и ошибки не размножаются. Фримен и Робинсон [99) рассматривали характеристики таких кодов для двоичного симметричного канала и показали, что они незначительно отличаются от характеристик блоковых кодов Хэмминга, исправляющих одиночные ошибки.

Класс сверточных кодов, исправляющих двойные ошибки, можно построить следующим образом (335). Согласно результатам разд. 9.2, при любом п2 существует двоичный примитивный (2 — 1, 2 — 2 — 2т)-код БЧХ с минимальным расстоянием 6. Его проверочная матрица имеет вид т 1 1 ... 1 1 1 п2И вЂ” 2 п2 — 3 и! пО ! пЗ(2 — 2) !гз(2 — 3) пз пО Н где Н; — двоичная матрица размерности и Х(2 — 1), а 1 — вектор-строка из единиц длины 2 — 1.

Тогда сверточный (2(2™ — 1), 2(2' — 1) — 2(лт+ 1) )-код с проверочной матрицей 1 Н, О 1 Н Н, Н= имеет расстояние И = 6. (Через О обозначена (2 — 1)-мерная вектор-строка нз нулей.) Это можно показать следующим образом для существования кодового слова веса 5 или меньше некоторая линейная комбинация из 5 или меньшего количества столбцов мат. рицы Н должна бы гь равна О. Среди первых 2'" — 1 столбцов магг!1 рицы Н следуег выбрать не менее 4 столбцов. Подматрица $ является проверочная матрицей кода Хэмминга с расстоянием 4.

Но, для того чтобы линейная комбинация символов в (т+ 2)-й строке равнялась нулю, надо выбрать не менее двух столбцов среди последних 2 — 1 столбцов матрицы Н. Таким образом, каждое слово имеет вес 6 или более. 13.4. Самоортогональные коды Эти коды составляют наиболее широкий конструктивный класс сверточных кодов [205, 259[.

К тому же их декодирование может осуществляться достаточно просто мажоритарным методом (см. гл. 10). К сожалению, при больших значениях п н й они имеют относительно малое кодовое расстояние. Ниже будут построены самоортогональные коды, у которых иь — йь = 1. Затем будет показано, что двойственным к самоортогональному сверточному (тпм т(па†1))-коду является самоортогональный (тп„т)-код. Коды, для которых иь — 1)йь >1, еще не найдены. В соответствии с равенством (3.14) основная проверочная матрица двоичного сверточного кода в систематическом виде при ив в Аь = 1 представляется как Ь = Ж ,О Р' ,О ...

Рь![, (13.3) где Р; — двоичная матрица-строка длины Аь. В самоортогональт ном коде с минимальным расстоянием д по меньшей мере г/ — 1 строк матрицы Н ортогональны (в указанном в равд. 10.1 смысле) относительно каждого из аь информационных символов нулевого блока. Матрица и может быть определена йз совокупностями целых чисел, выбранных из множества (О, 1, ..., т — 1). При этом /-я нз этих совокуппостсй определяет, какие из матриц-строк Рт имеют в /-й позиции 1, ! (/ 'Аь, т. е. в каком из блоков с номерами О, 1, ..., т — 1 соответствующий 1-й информационный символ проверяется проверочным символом в (т — 1)-и блоке.

Теперь необходимо дать определение разностноги треугольника, соответствующего упорядоченному множеству целых чисел [О, пь пь, па-а), где 0 Си, с п, ( ... (пг э[. Этот разностный треУгольник состоит из (с! — 1) (с( — 2)/2 Разностей и,— иь где / Если никакие две из этих разностей не совпадают, то говорят, что треугольник полный [211[. Если множества разностей двух ревностных треугольников не имеют общих целых значений, то такие разностные треугольники называются пеперссекаюа1ымися, Теорема 13.2. Пусть 5» 5ь .... 5м представляют собой множеств целых чисел, которые определяют сверточный (тпы т(пь — 1) )-код.

Пусть О принадлежит к ждому из множеств 5» Если Аь разностных треугольников, соответствующих этим множествам, полны, не пересекаются и состоят каждый из й — 1 элементов, то й — 1 проверочных сумм, представленных символами синдрома, ортогональны относительно каждого из Аь информационных символов нулевого блока и код имеет минимальное расстояние не меньше й. Более того, пт на единицу превышает наиболыиее целое число из этих множеств, Доказательство. Так как каждое из множеств 5, содержит й — 1 элементов, то любой из первых Аь столбцов матрицы В имеет вес й — 1 или.больше.

Остается показать, что й — 1 строк матрицы Н, которые соответствуют единицам в 1-м столбце матрицы В, ортогональны. Если две из этих й — 1 строк матрицы Н неортогональны, то они, кроме нулей, имеют в общей позиции единицу. Можно рассмотреть два случая; единица находится в 1-й позиции блока и в какой-нибудь,другой позиции. В первом случае в множестве 5, имеются такие две пары целых чисел (а„, Ь;) и (с» й;), что их разности а; — Ь; и с; — й; равны. Поскольку все разностные треугольники для множеств 5 полны, то этого быть не может. Рассмотрим второй случай, когда общая единица находится в 1-й позиции некоторого блока, ! ~'1. Пусть через а; и Ь; обозначены два целых числа из множества 5;. Если а~ — -а; = Ь; — Ьь то а; — Ь; = а,— Ь! и разностные треугольники множеств 5; и 5! пересекаются. Таким образом, имеется й — 1 ортогональных пооверочных сумм относительно каждого информационного символа декодируемого блока.

Ясно, что никакое кодовое слово не имеет вес меньше чем й, если блок с номером О является ненулевым. Ограничение на количество блоков в коде определяется количеством блоков, охватываемым множествами 5» Поскольку блок с номером О включается во все множества 5„то т — 1 равно наибольшему среди целых чисел по всем множествам 5» Ч. т. д. Следствие 13.1. Если самоортогональный код с блоковой длиной пь имеет минимальное расстояние й и йь = пь — 1, то его длина Это следствие вытекает нз того, что каждый из па†1 разностных треугольников имеет [(й — 1)(й — 2)/2! элементов, и эти треугольники не пересекаются. Пример. Самоортогональный код с расстоянием й = 5 и скоростью Й = й,/пь — — т/ь определяется двумя множествами из четырех целых чисел, таких, что ни одно целое число не появляется более диого раза среди шести разностей, образующих разностный треугольник, причем эти треугольники не пересекаются.

Множества целых чисел (0,8,9, 12) и (0,6, 11, 13) определяют полные непересекающиеся разностные треугольники 4 7 1 3 5 2 8 9 12 6 11 13 ()сновиая проверочная матрица, определяемая этими множествами, имеет вид Ь=[100 О!О 100 000 010 010 000 100 000 000 000 000 000 1! 11. (134) Заметим, что длина кода равна 42, т. е. совпадает со значением произведения лз на наибольшее целое число, входящее в разностные треугольники, к которому добавлена единица. Двойственным к самоортогональному (тпо, гп (пв — 1) ) -коду с минимальным расстоянием д . является самоортогональный (гппм т)-код с минимальным расстоянием д = (и„— 1) (И вЂ” 1) + 1. Если основная проверочная матрица первоначального кода опре- деляется равенством (13.3), то для двойственного кода Ро1 Р,О (13.6) Р,ОР ~О...Р~1 где Р; — матрица-столбец из (по — 1) символов.

Характеристики

Список файлов книги