У. Питерсон - Коды, исправляющие ошибки (1267328), страница 96
Текст из файла (страница 96)
При их построении используется в основном три метода: 1. Перемежение коротких кодов, исправляющих случайные ошибки. 2. Построение кодов, способных исправлять некоторые пакеты и некоторые случайные ошибки. 3. «Адаптивное» декодирование, при котором декодер пытается определить тип возникшей ошибочной комбинации и соответственно ее исправить. Блоковое перемежение степени 1 сверточных кодов, способных исправлять г случайных ошибок, дает в результате более длинный сверточный код, который может исправлять все пакеты длины [1/ло)1 или меньше, все комбинации ошибок веса 1 или меньше и много комбинаций ошибок с весом, несколько большим чем Среди последних находятся комбинации, которые можно классифицировать как многократные пакеты.
(См. задачу 14.12.) Во многих типах реальных каналов перемежение является наиболее подходящим средством для достижения малой вероятности ошибки. Хотя перемеженный код имеет относительно малое мини- мальное расстояние и малую гарантированную корректирующую способность для пакетов, эти два параметра оказываются зачастую довольно грубыми характеристиками возможностей кода.
Перемежение кода приводит к успеху, поскольку можно исправлять много комбинаций ошибок, не гарантированных этими параметрами. Самоортогональные коды, описанные в равд. 13.4, способны исправлять ! случайных ошибок и пакеты длины, обычно лишь несколько большей чем й Приведенные в предыдущем разделе коды Ивадаре, исправляющие пакеты ошибок, относятся к классу самоортогональных кодов с большой корректирующей способно.
стью для пакетов, но с ! = 1. Да4Ьфузные самоортогональные коды лежат где-то между этими двумя типами кодов. Рассмотрим самоортогональный сверточпый код, исправляющий ! случайных ошибок. Если этот код обладает такими свойствами, что для любого числа 1: 1) ни один пакет длины Ь или меньше, который начинается на 1-м информационном символе блока с номером 0 или до него, не может повлиять более чем на ! — 1 символов синдрома, используемого для декодирования этого символа, и 2) ни один пакет длины Ь или меньше, который начинается гделибо в другом месте, не может повлиять более чем на ! таких символов, то код может исправлять пакеты длины Ь или меньше.
Пример. Самоортогональный (20,10)-код с проверочной мат- рицей 11 00 11 00 00 10 00 00 10 00 00 00 00 10 00 00 10 1О 00 11 00 11 00 00 11 10 00 00 11 00 !О 00 00 11 00 00 10 00 00 11 00 00 00 1О 00 00 11 1О 00 00 00 1О 00 00 11 Н= имеет ! = 2 и Ь = 4, когда декодирование осуществляется мажоритарным способом. Четыре проверки, ортогональные относительно информационного символа блока с номером О, удовлетворяют условиям 1 и 2. Существует самоортогональный (14, 7)-код, для которого ! = Ь = 2.
За увеличение корректирующей способности для пакетов диффузного кода приходится платить увеличением длины ограничения. Фиг. 14.6. Кодер с й ячейками для адаптивной сверточиой кодирующей схемы Галлагера. Проблема построения диффузных самоортогональных кодов рассматривалась Гонгом (302( и Ивадаре [151). Вычислительные метод;ы, описанные этими авторами, подобны методам, используемым для построения самоортогональных кодов, исправляющих случайные ошибки, которые описаны в равд.
13.4 (259). Можно также строить и ортогонализируемые диффузные коды (151), хотя они к настоящему времени менее изучены, чем коды, представленные в этом разделе. (См., например, задачу 14.13.) Другой, привлекательный своей простотой метод защиты от пакетов и случайных ошибок при помощи сверточных кодов предложен Галлагером и описан Коленбергом и Форин (178(.
Этот чадаптивный» метод декодирования применим также и к блоковым кодам (101, 303). В объяснении, которое приводится ниже, предлагается система кодирования, для которой Ао = ив в 1 = 1. Обобщение на другие скорости проводится без труда. На фиг. 14.6 часть схемы, ограниченная пунктирной линией, представляет собой кодер исправляющего случайные ошибки кода с корректирующей способностью й Прежде чем будет передан проверочный символ блока с номером (У+ т — 1), к нему прибавится информационный символ блока с номером О. На практике У >) гп. Если происходят только случайные ошибки и базисный код может их исправить, то влияние ошибок в предшествующих информационных символах можно устранить, прежде чем декодируется блок 0 (фиг. 14.7).
Это нормальный режим работы. Если возникает длинный, плотный пакет ошибок, то корректирующая способность базисного кода будет превышена. Этот базис- иый код строится так, что только малая часть его смежных классов используется для исправления случайных ошибок. Таким образом с большой вероятностью ошибка будет обнаружена прежде, чем произойдет М ошибочных декодирований, т.
е. прежде, чем ошибочный символ выйдет из декодера. На данном этапе декодер предполагает, что он обнаружил начало пакета длины 2/У или меньше, половина которого лежит в информационном регистре. Ключ 4 открывается, а ключ 3 закрывается (в соответствии с пунктирной линией на фиг. 14.7), и символ синдрома из блока Л~+лт — 1 добавляется к информационному символу блока с номером О.
При отсутствии ошибок в блоках с номерами от /У + т' — 1 до /У + т — 1 + 1Ь/21 декодер исправит любой обнаруженный пакет длины Ь ~ 2Ь/. Конец пакета может быть обнаружен тем же способом, что и его начало — схемой обнаружения пакета. Когда декодируется некоторое количество блоков, у которых синдромы полностью состоят из нулей, декодер вновь возвращается к режиму работы со случайными ошибками. Количество блоков, как н величины т, /У, М н 1, является конструктивным параметром, который должен выбираться в зависимости от характеристик канала и требований к системе в целом.
По этой схеме кодирования отношение максимальной корректирующей способности для пакетов к защитному пространству Ь 2Ф я 2Ф+и близко к единице для значений М и гл, представляющих практический интерес. Заметим, однако, что не все пакеты длины ~ 2/ч' могут быть исправлены. БПМ-коды, являющиеся наилучшими из ранее описанных при /1 = 0,5, могут быть декодированы при отношении Ь/а ж /по/2/по = 0„5. Эти коды являются оптимальными 1выражепие (4.67)], если необходимо исправлять все пакеты длины Ь. В схеме Галлагера некоторые пакеты длины, значительно меньшей чем Ь, не исправляются.
При соответствующем выборе параметров кода это, однако, может не иметь решающего значения н в значительной степени компенсироваться удвоением эффективной корректирующей способности кода для пакетов, Замечании Первые сверточпые (рекуррентные) коды, исправляющие пакеты ошибок, были найдены Хегельбергером [132, 133]. Эти коды изучались также Килмером [174]. Вайнер н Эш [334] определили коды типа В2 и нашли границу, приведенную в выражении (14.!). Их результаты использованы Берлекэмпом и Препарата прн построении кодов, описанных в равд.
14.2; Месси предложил процедуру декодирования для базисных БПМ-кодов. Ивадаре развил работу Хегельбергера н Питерсона [234, гл. 12] и нашел коды, описанные в равд. 14.3. Диффузные коды впервые предложены Месси и описаны Коленбергом [177]. Недавно Ивадаре [15!] н Тонг [303] достигли некоторого успеха в проблеме построения этих кодов. Схема Галлагера, описанная в равд. 14.5, по-видимому, хорошо приспособлена для каналов с плотными пакетами, разделяемыми мало зашумленными промежутками; для некоторых других каналов, по-видимому, имеют преимущество перемеженный код, исправляющий случайные ошибки, и диффузный код. Задачи 14.1.
Сравните отношение Ь/и для наилучших сверточных кодов, исправляющих пакеты, и блоковых кодов при Ь =1000 и й = 1/а. Разъясните выводы. 14.2. Хотя это обычно и не делается, понятие «длины ограниченна» для блоковых кодов можно определить так же, как и для сверточных. Пусть через и, обозначено наибольшее количество символов, которое охватывается символами, участвующими при декодировании произвольного информационного символа некоторого кодового слова. Рассмотрите блоковый код, являющийся результатом перемежения степени 1000 циклического (3, 1)-кода, порожденного многочленом Х'+ Х+ 1.
Сравните отношение Ь/и, для этого кода с аналогичным отношением из задачи 14.1. Разъясните выводы. !4.3. Покажите, что символьное перемежение сверточного (тп,, т/га)-кода приводит к коду с длиной блока /па, Иа информационными символами на блок и т блоками на длине ограничения. Покажите, что блоковое перемежение приводит к коду с длиной блока пе, Ае информационными символами на блок н (т — 1)1+ 1 блоками на длине ограничения. Рассмотрите эту задачу с точки зрения реализации. 14.4.
Пусть дап сверточный код с Ьа = пе, где Ьа лежит на границе, выражаемой в виде равенства и описываемой теоремой 4.!8. Докажите, что блоковое перемежение всегда приводит к коду, также лежащему на этой границе. Сравните с символьным перемеженнем, 14.5 !!8). Покажите, что для (8, 4) -кода с 01 00 10 1О значение Ь 2.
Покажите также, что для (18, 12)-кода с 101 100 !00 010 000 010 Бо= значение Ь = 3. (Эти коды были найдены после просмотра всех матриц данных размеров.) 14.6. Постройте декодер для двух кодов из предыдущей задачи; используйте идеи из равд. 14.3. Модифицируйте схему для (8,4)- кодов с тем, чтобы проводить декодирование в случае, когда осуществляется перемежепие кода степени 10. 14.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
