У. Питерсон - Коды, исправляющие ошибки (1267328), страница 82
Текст из файла (страница 82)
Кодирование может быть проведено способом„описанным в равд. 8.7. Схема кодирования показана на фиг. !1.2, а декодер — на фиг. 11.3. Заметига, что обратная связь регистра сдвига идентична той, которая применялась при кодировании. Процесс исправления ошибок состоит из следующих шагов. 1. Весь принятый вектор записывается в буферном устройстве и одновременно в генераторе синдрома, который сдвигается по Ваао0 Фиг. 11.2. Кодер (279, 265)-кода Файра. йуоеерка на осе нули Бурерное усшройапео Фиг.
11.3. Схема исправления ошибок кодом Файра, кодер которого искании иа фиг. 11.2. мере поступления каждого символа, (Ключ 1 открыт, т. е. дает возможность входной последовательности перемещаться к выходу. Ключ 2 закрыт.) 2. Затем принятый вектор считывается с буферного устройства, по одному символу в каждый момент времени, а регистр сдвига сдвигается на один разряд для каждого символа, причем на вход регистра сдвига ничего не подается. 3. Когда в первых девяти ячейках появятся только нули, в последних пяти ячейках должна появиться комбинация ошибок, и ошибочные символы будут готовы к выводу из буфера. При этом ключ 1 закрыт, ключ 2 открыт и происходит исправление символов.
Если в первых девяти разрядах появятся не только нули, это будет означать, что обнаружена неисправимая комбинация ошибок. Может оказаться желательным укоротить код, исправляющий пакеты ошибок, либо потому, что пакеты ошибок появляются слишком часто, либо потому, что общая длина или число информационных символов в коде ограничены другими требованиями, накладываемыми на систему. Если нельзя найти код подходягцей естественной длины, то можно укоротить код, просто заменяя некоторые из его информационных символов высших порядков нулями и отбрасывая их. Это не потребует изменения методов кодировании и проведения проверок на четность„поскольку при этом несущественно наличие нулей в начале информационных символов. Однако такая замена потребует изменения описанного выше процесса исправления ошибок. Предположим, например, что используется код, естественная длина которого равна и, но з информационных символов его отброшены.
Тогда для исправления ошибок первоначальным способом до того, как начинается считывание полученного вектора из буферного запоминающего устройства, потребуется з сдвигов, соответствующих з отброшенным информационным символам, в предположении, что все зти символы равны О. Один из способов некоторого упрощения этого процесса состоит в предварительном автоматическом умножении на Х' по модулю д(Х) с использованием схемы умножения, изображенной на фиг. 7.8. Этот прием иллюстрируетсн следующим примером: Пример. Предположим, что нужен двоичный код, исправляющий любой пакет ошибок длины 5 и содержащий 200 информационных символов. Можно испольэовать код, описанный в предыдущем примере, если заменить в нем 65 информационных символов высших разрядов нулями и отбросить их.
Для кодирования может быть использовано то же самое кодирующее устройство. Результаты проверок на четность, очевидно, равны вычету по модулю д(Х) многочлена Х"г(Х). Требуется провести дополнительное автоматическое умножение на Хаз, т. е. нужен вычет много- члена Хмг(Х). Найденный в результате длинных вычислений ос- таток от деления Хтз на д(Х) равен Хм+ Хп + Хм+ Х»+ Х7+ Х«+ Х2+ Х+ 1, Схема, применяемая для исправления ошибок этим кодом, показана на фиг. 11.4. Она используется также как схема, изображенная на фиг. 11.3, и отличается только тем, что здесь кодовые слова содержат 200 информационных символов и 14 проверочных символов.
Если для получения удлиненного кода, исправляющего пакеты ошибок, проводится перемежение степени 1 циклического (или укороченного циклического) кода, то удлиненный код можно декодировать тем же способом, что и циклический (или укороченный циклический) код. Каждое из 1 принятых коротких слов можно декодировать независимо; однако реализация декодера в этом случае будет несколько сложнее, ибо каждое слово перед исправлением должно быть выведено из буфера и синдромного регистра. Описываемая далее статистическая процедура исправления пакетов была предложена Галлагером 1103).
Ненулевые символы любого синдрома расположены в пакете длины и — А или меныпе. Таким образом, произвольный смежный класс содержит набор длины и, все ненулевые символы которого расположены в пакете длины п — й или меньше. Поэтому если иметь дело только с исправлением пакетов, то в качестве лидера смежного класса может быть выбран пакет длины и — й или меньше. Простое видоизменение процедуры декодирования пакетов длины Ь обеспечивает исправление всех пакетов длины и — А или меньше, которые можно в принципе исправить. В приведенном ниже описании этой процедуры предполагается„что используется циклический код; модификации при переходе к укороченным циклическим кодам очевидны. Рассмотрим схему, приведенную на фиг. 11.1.
После вычисления сдвинутого синдрома декодер сдвигает и раз регистр синдрома и определяет длину Л укороченного пакета, который появляется в синдромпом регистре. Это может быть сделано путем вычитания из и — й числа, равного наибольшему количеству нулей, последовательно появляющихся на выходе из генератора. (Пакеты, которые перекрывают концы слов, не учитываются.) Позиция первой ошибки из пакета записывается.
Исправление происходит в соответствии с процедурой, описанной ранее. Здесь, однако, не требуется логических элементов «ИЛИ», поскольку положение пакета известно. Необходимо только прерывать обратную связь в генераторе синдрома в моменты, когда первый символ пакета появится в ячейке генератора наивысшего порядка. Затем все содержимое генератора добавляется последовательно к выходу буферного регистра. йюнерла на ага н ли Фиг* 11А.
Схема исправлении ошибок кодом Фвйра (фиг. 11.2)„укорочениым иа 79 символов. Всего имеется один пакет нулевой длины, а пакетов длины, рави й 1 н (и — 1+1)2г-х пакетов длины й Таким образом, общее число пакетов длины ь или меньше равно Ь + „+ х; („,. + 1) 2г-г 2~+ма оим ю 2 Но поскольку число смежных классов составляет 2 -", то их достаточно, чтобы исправлять все пакеты длины а — й — !од(п/2). При больших значениях й и и — й эта величина существенно больше, чем гарантированная длина исправляемых пакетов ошибок, которая ограничена сверху числом (и — л)/2. Например, циклический (150,90)-код, получаемый перемежением степени 1О (!5,9)-кода, указанного в табл.
1!.2, имеет корректирующую способность для пакетов, равную 30. Однако 2аэ смежных классов достаточно для того, чтобы исправлять все пакеты из 53 символов или меньше. Конечно известно, что существуют неподдающиеся исправлению пакеты ошибок длины (и — й)!2+ 1 или меньше. Тем не менее приведенное выше обсуждение показывает, что может быть исправлено большое число длинных пакетов ошибок. В работе Гал, патера !103) приведены верхняя и нижняя границы для числа исправимых пакетов ошибок длины Е., где Ь ( Е. ( п — А. 11.4.
Исправление многократных пакетов В некоторых каналах пакеты могут возникать столь часто, что их нельзя исправлять с помощью кодов, исправляющих одиночные пакеты ошибок. Это имеет место, если, например, есть тенденция к образованию групп из пакетов ошибок.
В таких каналах желательно применять коды, которые могут исправлять более чем один пакет ошибок в каждом блоке. Класс кодов Рида — Соломона — наиболее мощный из извест. ных классов кодов, исправляющих многократные пакеты ошибок. Однако алгоритмы их декодирования (см. равд. 9.4 — 9.6) значительно сложнее, чем соответствующие алгоритмы для исправления одиночных пакетов ошибок, изложенные в предыдущих разделах. Можно трактовать (д~ — 1, д"' — 1 — 21) -код Рида — Соломона над полем ОР(д"') с кодовым расстоянием д = 21+ 1 в ОЕ(д ) как ((9 — 1)пг, (д — 1 — 21)гл)-код над полем СЕЯ, который может исправлять любую комбинацию ошибок, сосредоточенную в 1 или меньшем числе блоков из т символов. Так как наибольшее число блоков из т символов, которые может затронуть пакет длины 1„где 1; ( ги1; — (т — !), не превосходит (ь то код, исправляющий 1 блоков ошибок, всегда может исправить и любую ком- бинацию из р пакетов общей длины 1, если только 1+(и — 1) р(гпй (11.
13) Код, исправляющий 1 ошибок, после перемежения степени 1 может исправлять все одиночные пакеты длины 11 или меныпе, два произвольных пакета длины (11/2) или меньше и т. д., вплоть до 1 произвольных пакетов длины 1 или меньше. Оказалось, что это наиболее эффективный с практической точки зрения подход к исправлению многократных пакетов ошибок в реальных каналах некоторых типов. Кроме того, и циклические коды, исправляющие случайные ошибки, обладают некоторой способностью исправлять многократные пакеты. (См. теорему 11.4.) 11.5.
Исправление пакетов и случайных ошибок Если код имеет корректирующую способность для случайных ошибок 1 и: корректирующую способность для пакетов Ь н смеж. ные классы, содержащие комбинации ошибок веса 1 или меньше, отличаются от классов, содержащих комбинации пакетных ошибок (исключая, конечно, случай, когда комбинацию можно отнести к обоим этим типам), то он может исправлять ошибки обоих типов.
Некоторые классы конструктивных кодов, построенных аналитическим способом, обладают таким свойством. Среди них наиболее мощным классом является класс, который образует коды Боуза— Чоудхури — Хоквингема и, в частности, коды Рида — Соломона. В равд. 11.! отмечалось, что код Рида — Соломона над 6Р(п ) может исправлять все пакеты длины пг1 — т+ 1, если его рассматривать как код над 6Е(о).
Поскольку каждый такой пакет имеет вес, не больший чем 1 [над 6Р(д )), то смежные классы, содержащие пакеты 1над 6Р(д)), отличаются от смежных классов, содержащих комбинации ошибок веса 1 или меньше 1над 6Е(д)). В задаче 11.6 рассматривается несколько менее эффективный метод построения кодов, исправляющих пакеты и случайные ошибки. В теореме 5.2 утверждается, что коды-произведения также обладают этим свойством. В статье 1145) табулировапы некоторые классы двоичных кодов, полученных с помощью ЭВМ, которые могут исправлять пакетные и случайные ошибки.
Для многих из этих кодов при фиксированном значении 1 величина Ь несколько больше, чем для укороченных кодов Рида — Соломона при той же длине и скорости. Любой (п,й)-код имеет 2"-" смежных классов и используе~ С„' смежных классов для исправления всех комбинаций веса 1 ь-а или меньше. Для наиболее известных кодов уже при умеренно с больших значениЯх п отношение ~„С' с12" достаточно мало. с-е Лналогично мала и та часть смежных классов, которая исполь тся для исправления всех пакетов длины 6 =(и — й)сс2. Таким образом, нет причин, чтобы априори предполагатгч что хороший код, исправляющий случайные ошибки, не сможет также исправлять достаточно длинные пакеты. Коды Су, Касами и Цяня [145] это подтверждасот.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
