У. Питерсон - Коды, исправляющие ошибки (1267328), страница 93
Текст из файла (страница 93)
Месси построил также (методом проб и ошибок) ортогона. лизируемые коды, описанные в равд. 13.5. Вайнер и Эш (334) на- шли коды, исправляющие одиночные ошибки (разд. !3.3), и создали значительную часть математического аппарата теории сверточных кодов. Авторами кодирующих схем, содержащих й н и — й ячеек памяти, которые обсуждались в разд. 13.1, являются соответственно Возенкрафт н Рейффен [333[ и Месси [205[. Одной из важнейших нерешенных проблем алгебраической теории кодирования является построение хороших сверточных кодов, исправляющих многократные ошибки. Граница Гилберта из гл. 4 и коды, полученные на ЭВМ Лином и Лайном [185) н Бассганом [38), показывают, что такие коды существуют.
Последовательное декодирование предложил Возенкрафт [330]. Алгоритм, приведенный в разд. 13.8, предложен Фане [801 Дальнейший вклад в развитие этого метода сделан многими другими исследователями, главным образом из Массачусетского технологического института. Было реально построено несколько последовательных декодеров, и прн быстро снижающейся стоимости вычислительных средств представляется, что этот самый мощный метод будет в дальнейшем широко использоваться. Основной недостаток этого метода — чувствительность к пакетным ошибкам, что ограничивает его использование каналами, которые достаточно близки к каналам без памяти. Алгоритм Витерби [312), приведенный в равд.
13.7, как и последовательное декодирование, использует длину ограничения при декодировании п, которая значительно больше длины кодового ограничения п,. Для этого алгоритма количество действий в большей степени зависит от и„ чем от п, тогда как вероятность неправильного декодирования пропорпиональна 2-"Я<п!, где Е(1т)— обычная экспонента вероятности ошибки. Это приводит к новой экспоненте вероятности ошибки Р 2 в рп — 2 ь!"а !апМ е 'Максимизнруя отношение п!п„величину пЕ(й)!п, можно сделать значительно больше, чем соответствуюгцая экспонента вероятности ошибки для блокового кода, особенно при скоростях, близких к пропускной способности.
Изложение алгоритма Витерби в равд. 13.7 основано на работе Джекобса, Витерби и Хеллера [!52). Задачи 13.1. Сравните скорости передачи для укороченного кода Хэмминга и исправляющего одиночные ошибки сверточного кода приблизительно одинаковой длины. 13.2. Обобщите метод, применяемый в равд.
13.3, для построения кодов, исправляющих двойные ошибки. Постройте сверточный (62,22)-код с д = 8, используя проверочную матрицу (31, 10)-кода БЧХ с с(=12, 13.3. Постройте схему декодера для исправляющих двойные ошибки кодов, описанных а равд. 1З.З. 13.4. Попытайтесь построить систематический ортогонализируе. мый сверточный код с по= 3, йо= 2 и з(= 5, длина которого меньше, чем самоортогонального (42, 28) -кода из примера разд 13 4, Эта задача указывает на трудности, возникающие при распространении конструктивного метода проб и ошибок на скорости больше чем '/з.
13.8. Постройте дерево для равномерного сверточного (12,3)- кода из разд. 13.5. Проверьте, что для этого кода д = 8. Прилагательное «равномерный» указывает на постоянство весов кодовых слов в неправильном подмножестве (нижняя половина дерева). 13.8. Пайдитс ортогональные соотношения для декодирования равномерного сверточного кода с т = 4. 13.7.
Понятие эффективного ограничения длины пзее было использовано при определении вероятности первой ошибки для самоортогонального и ортогонализируемого сверточного кода. Пусть п,ее — количество символов, требующихся при декодировании по символов блока О. Покажите, что для кода, исправляющего 1-кратные ошибки в ДСК с вероятностью ошибки Р, вероятность первой ошибки »йе $-з+1 13.8. Порождающая матрица произвольного несистематического кода с Ао —— по — Йо — — 1 может быть с помощью перестановок столбцов преобразована к виду О =(Р,Р,).
Матрица Р; размерности (т Х т) имеет вид 1 РзРз Р Рз (13.22) Рз О ° Рз где Р; — произвольные д-ичные числа. Пайдите проверочную матрицу этого кода. Определите, при каких условиях матрица Н представляется в виде Н ~рз Рй где матрицы Рз и Рз такие же, как в (13.22). 13.9. Двоичный (12,6)-код с порождающей матрицей 11 ОО ОО 01 О! 01 Г !1 00 ОО 01 01 11 00 00 01 11 00 00 !1 00 11 имеет длину кодового ограничения 12.
Если ограничение длины при декодировании тоже равно 12, то код имеет минимальное расстояние 5. (См. равд. 13.5.) Производя элементарные операции над строками, постройте несистематический вариант этого кода с длиной кодового ограничения 8. Если ограничение длины прн декодировании теперь уменьшено до 8, можно ли все еще исправлять произвольные комбинации ошибок веса 2г 13.10. а) Постройте модифицированную диаграмму состояний свергочного кода с йа = па — Аа — — 1, д,(Р) = 1+ Р+ Рз+ Р4 и о (Р) 1 ! Рз ( Р4 б) Определите передаточную функцию Т(Р, Е) и г(„.
13 !1 !2161. Пусть полипом д(Х) порождает двоичный циклический код длины п с минимальным расстоянием д; о — минимальное расстояние двойственного кода, порожденного многочленом й(Х) = (Х" — !)(д(Х). Покажите, что систематический сверточный код с Й = '/х при д,(Р) = 1 и д,(Р) = д(Р) имеет расстояние д,„) ш!п[Н+ 1„д+ 21. 13 !2.
Используя результат предыдущей задачи и (23,12)-код Голея, постройте сверточный код, исправляющий четырехкратные ошибки. ) 4 Сверточные коды, исправляющие пакеты ошибок В этой главе рассматривается несколько классов сверточных кодов, исправляющих как одиночные пакеты ошибок, так и комбинации пакетных и случайных ошибок. 14.1. Некоторые определения Говорят, что сверточный (тпмтйа)-код имеет корректирующую способность для пакетов ошибок типа В2, равную Ьт — — гпм если он может исправлять все пакеты длины Ьм ограниченные г последовательными блоками, и не исправляет по меньшей мере один пакет длины (г+ 1)пь. Корректирующая способность кода для пакетов ошибок Ь связана с корректирующей способностью кода для пакетов типа В2 следующим образом: (14.1) Ь,+ (,— 1) ~Ь~Ь,— (, — 1).
Эта верхняя граница для Ь и верхняя граница для Ьз из тео. ремы 4.18 совместно дают результат, сформулированный в теореме 4.19: Ь( (т 11(пь ~01 + 1 (14.2) 1+— Йа пд Коды, построенные в следующих далее разделах, очень тесно приближаются к этой границе особенно при больших значениях тиЬ. Рассмотрим код с корректирующей способностью для пакетов Ь, для декодирования которого применен некоторый декодер. Пакет длины 1( Ь исправляется, если за ним следует соответствующее количество правильных символов. Минимальное количество таких символов образует защитное пространство, требуемое для исправления этого пакета.
Максимальное защитное пространство, требуемое для исправления произвольного пакета, называется защитным пространством кода. Будет показано, что защитное пространство кода зависит от того, как декодируется код. Вообще говоря, желательно минимизировать защитное пространство, ибо ошибки в канале, происходящие в соответствующий период, могут вызвать неправильное декодирование. Для произ- вольного (и, е)-кода защитное пространство д ограничено величиной д--и — 1.
(14.3) Для некоторых типов кодов д=п — Ь, (14.4) неизмененные Фаг. !4.1. Кодер сверточпого 18,4)кода при а= 10010 100Ц. и на практике д не может быть значительно меньше чем и — Ь. Основная идея, использованная прн построении всех сверточных кодов, исправляющих пакеты, состоит в том, что символы, применяемые при декодировании некоторого символа, распределены во времени так, что только один, в крайнем случае несколько из них, может быть затронут одиночным пакетом ошибок.
Наиболее простой путь достижения такой длительности состоит в переткежении. При этом методе поток данных по существу разделяется на 1 независимых потоков: параметр ! называется степенью переиежения. Имеется два основных способа перемежения сверточного кода. При силеальнои перележении символы с номерами 1, 1+ 1, 21+ 1, ... кодируются независимо от всех других символов. При блоковом перемежении блоки из по символов, разделенные 1 блокамн, образуют независимый поток данных. Если для базисного кода Ь ( по, то блоковое перемежение применять нельзя. Однако коды, рассмотренные в равд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
