У. Питерсон - Коды, исправляющие ошибки (1267328), страница 95
Текст из файла (страница 95)
Если код декодируется с помощью процедуры исправления одиночных пакетов, то д = л — ов Таким образом, в каналах, где возникают только редкие длинные пакеты ошибок и важно иметь короткое защитное пространство, только что описанная процедура декодирования предпочтительнее. Однако в более реальных каналах возникают многократные пакеты и комбинации пакетных и изолированяых «случайных» ошибок, поэтому здесь, вероятно, лучше использовать независимое декодирование потоков из ! символов. Схемы декодирования для этих двух процедур почти одинаковы. (См. задачи 14.7 и 14.9.) Кроме того, размножения ошибок в каждом из декодеров не происходит, так как после исправления синдром полагается равным пулю.
14.3, Коды 14вадаре =""', "+(2 -!), йо= ло Ь=лэ, д=п — 1 (14.12) при любых лз) 2. Заметим, что эти базисные коды в отличие от базисных БПМ-кодов исправляют все пакеты длины и» независимо от фазы. Представленные в этом разделе коды, исправляющие пакеты ошибок (15!), определены при йо = л,— 1. Они, по-видимому, несколько проще в реализации, чем БПМ-коды той же скорости и с той же корректирующей способностью для пакетов, хотя и требуют несколько большее защитное пространство.
Базисный код Ивадаре имеет параметры Проверочная матрица кода определяется матрицей Вм которая имеет вид ~с=не — ь~ 0 ... 0001 0 ... 0000 в = (14.13) 01 ... 0000 10...0000 ~ оо ... Оооо ! пО ! 10...0000 т где 1-й столбец матрицы Во, 1 = ! ~ лз — 1, имеет единицы только в позициях с номерами , (.(а.— В(.— (+))~ Г(ПΠ— 1) (ло — 1+ !) (+ Пример, Пусть пз — — 3. Тогда матрица 001 1 001 001 010 ~ 001 010 ~ 010 100 ! 010 010 114,14) 001 001 ! 001 000 001 000 010 010 010 100 010 000 100 100 00 ... 0000 О ...ОО!О 0 ...
0010 0 ...0100 0 ... 0000 0 ... 0100 Т по е 2 3 ( является проверочной матрицей (24,16)-кода Ивадаре с коррек- тирующей способностью для пакетов Ь = 3. Как обычно, пустые места заполняются нулями. Процедура декодирования кодов Ивадаре существенно отличается от всех ранее обсуждавшихся методов декодирования тем, что по — ! информационных символов каждого блока декодируются в разные моменты времени.
В частности, символ с номером п,— 1 декодируется после приема по+ 2 блоков, символ с номером и — 2 — после приема па+2+3 блоков, ..., первый символ— после приема т = по+ 2+ 3+ ... + л, блоков. Таким образом, декодирование осуществляется в па — 1 этапов. Пример (продолжение). Код Ивадаре с ле = 3 имеет два информационных символа на блок.
Второй из них декодируется после приема 5 блоков с использованием двух ортогональных проверочных сумм (строки 4 и 5) подматрицы (14.14), очерченной пунктирной линией. Можно исключить влияние ошибок во втором информационном символе, прежде чем исправлять первый информационный символ. В результате матрица, используемая для декодирования этого первого символа, представляется в виде (14.15) 001 001 ! 001 Декодер для этого кода показан на фиг. 14.4. Заметим, что только два из восьми символов синдрома действительно используются для исправления. Вообще для исправления необходимо только ле — 1 символов синдрома.
Чтобы увидеть, что код Ивадаре действительно имеет корректирующую способность Ь = п„необходимо только проверить в общей матрице вида (14.15), что: 1) для каждого информационного символа имеется две ортогональные проверочные суммы; 2) в силу структуры матрицы Н никакой пакет длины ла нли меньше не может привести к срабатыванию элемента «И» (фиг. 14.4) в ненужный момент времени, Заметим, что одна из двух проверочных сумм вг гда имеет вес два, и для того, чтобы пакет исказил их обе, он должен иметь длину па+ 1 или больше. 001 000 000 000 000 100 000 100 001 001 -, 001 001 100 1 010 100 ! 010 010 Испрдалсиныс сиисалы + Вкрд Фнг. 14.4.
Декодер (24, 1б)-кода Ивадаре при ее =Ь 3. для кодов Ивадаре требуется защитное пространство, равное 1 символам. Это видно из того, что первый информационный имвол будет декодироваться неправильно, если проверочный символ в блоке с номером и — 1 ошибочен. Перемеженне кодов Ивадаре может производиться обычным способом, в результате чего по,пучаются коды, которые хуже, чем ВПМ-коды с той же скоростью и корректирующей способностью. ()днако коды Ивадаре поддаются неравномерному перемежению, благодаря чему они имеют некоторые преимущества перед БПй(- кодами. При блоковом перемежении сверточного кода степени ! в матрицу Ва под каждую строку первоначальной матрицы вставляется !†! нулевых строк.
Только вторая строка и все ненулевые строки матрицы В„исключая последнюю, подвергаются перемежению в кодах Ивадаре. При этом получаютсн коды со следующими параметрами: т=(2пэ — 1)1+ 2 но= по — 1~ Ь= !л„ д= л — 1. (14.16) 001 000 000 000 000 010 000 010 000 100 000 000 100 Пример. Если (24.16)-код из предыдущего примера подвергается перемежению степени 2 так, как описано ранее, то результирующий (39, 26)-код имеет проверочную матрицу, определяемую матрицей + лслравленпие сллгволи блюл Вход ЯН лЦ ВЕи Фиг. 14.5. Декодер е39,26)-кода иаадаре при с =6.
декодирование осуществляется, как и для исходного кода, когда второй информационный символ декодируется раньше первого. Та„им образом, матрица, соответствующая матрице вида (14.5), представляется в виде ГОО! ОО! ОО! ОО! 001 оО! 010 о!о 1 о1О О1о (14.17) Корректирующая способность для пакетов этого кода равна 6.
Если возникают пакеты длины 4, 5 и 6 с ошибками в местах, обозначенных знаком «, то зти пакеты будут исправлены. Однако элемент «И» для второго информационного символа будет введен в действие и вызовет ошибочное исправление. Этой трудности можно избежать, запретив работу второго элемента «И»„в ситуации, когда действует первый э.аемент «И». Декодер для этого кода приведен иа фиг. 14.5. Запрещение работы второго элемента «И» достигается за счет использования одного элемента «НЕ», соединенного с выходом первого элемента «И». Вообще А-й элемент «И» подавляется !ьм элементом «И» при ! ~ й. Защитное пространство, необходимое для перемеженных кодов Ивадаре, как и для базисных кодов, равно и — 1.
Это доказывается с использованием тех же соображений, что и раяее. Вообще защитное пространство для декодера Ивадаре несколько больше, чем для соответствующего БПМ-декодера, исправляющего одиночные пакеты. Однако стоимость реализации последнего может быть несколько больше.
(См. задачи 14.7 и 14.10.) оо! ООО ОО! ООО ОО! ооо ОО! ооо оо! ооо ооо ооо ооо 1ОО 000 100 000 100 1! ОО 100 1 ) 1 3 1 001 ! Оо! 1 14.4. Низкоскоростные коды Наиболее известные коды, исправляющие пакеты ошибок, при скоростях 1/лм по = 3,4, 5, ... имеют следующие параметры: т=3, л=п,,лт= и„ (14.!8) "о= 1. а=-л — 1. Матрица Ва для таких кодов принимает вид (14.19) где а — нулевой столбец длины па — 1, Ь вЂ” столбец длины по — 1, содержащий нули всюду, кроме позиции с номером [аа/2], где стоит единица, и с — столбец, содержащий всюду нули, кроме одной еди- ницы в позиции с номером и,— 1. Пример.
Сверточный (9,3)-код, исправляющий пакеты ошибок, с параметрами ло = 3, lгс — 1, Ь = 4 и и = 3 определяется мат- рицей 010 001 !00 000 000 100 Во= Чтобы убедиться в том, что для кодов этого типа Ь = [(п — 1)/2), необходимо только показать, что не существует кодового слова с ненулевым первым блоком, все единицы которого ограничены двумя пакетами длины [(л — 1)/21 = ло+ [(ле — 1)/2). Если первый блок ненулевой, то его информационный символ равен 1. Следовательно, символ второго блока с номером (1+[по/2)) и последний символ третьего блока также равны 1, и кодовое слово действительно не содержит двух или меньшего числа пакетов.
Поскольку корректирующая способность для этих кодов удовлетворяет верхней границе, задаваемой соотношением (4.68), то они оптимальны. Декодирование этих кодов осуществляется просто. Если возникает пакет ошибок длины Ь или меньше и информационный символ первого блока искажен, то не будут удовлетворяться два проверочнеых соотношения для этого символа. В противном случае удовлетворяется одно или оба из этих проверочных соотношений. Если также искажен информационный символ второго блока, то он буисправлен аналогичным образом после вывода из декодера первого блока.
Согласно теореме !3.1, в этих кодах не происходит размножения ошибок. В результате перемежения со степенью 1 кодов, параметры которых выражаются равенствами (14.18), получается класс кодов, для которых т= 2(+ 1, п=п,гп, (14.20) йо= 1~ Д=п — 1, где по — произвольное число. Заметим, что эти коды оптимальны в том смысле, что они лежат на границе, задаваемой неравенством (4.63). 14.5. Коды, исправляющие пакеты ошибок и случайные ошибки В этом разделе представлены сверточные коды для исправления комбинаций ошибок, которые не обладают малым весом и не располагаются в виде одиночного пакета ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
