У. Питерсон - Коды, исправляющие ошибки (1267328), страница 55
Текст из файла (страница 55)
Таким образом, комбинационной схеме декодера Меггита достаточно только обнаружить наличие исправляемой комбинации ошибок в регистре синдрома, содержащей ненулевые символы в разрядах высших порядков. Фактически может быть более удобным некоторое видоизменение декодера Меггита. Комбинационная схема должна обнаружить только наличие исправляемой комбинации ошибок в некоторых разрядах регистра синдрома и затем вычесть содержимое регистра синдрома из содержимого разрядов высших порядков буферного устройства. Заметим, что при вылавливании ошибок в случае, когда и — А разрядов, содержащих комбинацию ошибок, частично являются разрядами высших порядков, а частично разрядами низших порядков первоначального содержимого буферного устройства, разряды высших порядков не будут исправляться в течение первых и сдвигов.
Эту трудность можно устранить, вычисляя первоначальный синдром путем деления г(Х) на д(Х) без предварительного умножения иа Х -". После этого осуществляется и — А сдвигов регистра синдрома и каждый раз проводится сравнение для обнаружения исправляемой комбинации. Если такая комбинация появляется, то ошибки и разрядах высших порядков могут быть исправлены немедленно; в противном случае, как описывалось выше, потребуется А дополнительных сдвигов генератора синдрома и полученного вектора. Метод вылавливания ошибок эффективен, если можно ограничить все комбинации ошибок п — А последовательными разрядами.
Очевидно, что это возможно для всех кодов, исправляющих одиночные ошибки, и фактически для всех кодов, исправляющих пакеты ошибок. Для кода, исправляющего все пакеты длины Ь или меньше, комбинационная схема может быть описана следующим образом. Выход равен нулю, если какой-либо из п — А — Ь симво- лов ячеек низших разрядов в регистре синдрома отличен от нуля; в других случаях он равен взятому с противоположным знаком символу из соответствующей ячейки высшего разряда в регистре синдрома. Для двоичного случая это просто схема «И» с л А — 6+1 входами, на которые подаются отрицания первых л А — 6 символов и правильное значение последнего символа из регистра синдрома.
Можно показать, что при наличии случайных ошибок необходимым и достаточным условием для исправления всех комбинаций из 1 или меньшего числа ошибок, содержащих по меньшей мере А последовательных нулей, является выполнение неравенства 1( —, (8.23) где Я вЂ” скорость кода А/л. (См. задачу 8.!О.) Был предложен ряд модификаций метода декодирования вылавливанием ошибок, расширяющих границы применимости этого метода. Вариант этого метода, который будет сейчас описан, является хорошим методом декодирования для многих коротких циклических кодов, в том числе для (23, 12)-кода Голея, рассматриваемого ниже в качестве примера. Представим комбинацию нз трех ошибочных символов в виде цикла, состоящего из трех единиц с расположенными между ними наборами нулей длины 5ь 5з и5з.
Тогда общее число нулей равно 5,+5з+ 5з — — 20. Допустим, что Ьз ) 5э ) 5ь Для тех комбинаций ошибок, которые не могут быть исправлены обычным методом вылавливания, 5, ( А = 12 и, следовательно, 5, + 5з ~ 8. Но поскольку 5з ) 5ь то 25з ) 8 и 5э ) 4, т. е. 5з) б. Если 5з б, то при 5~ (5, отсюда следует, что 5з ) 10. Таким образом, одна из трех единиц в комбинации ошибок имеет по меньшей мере пять нулей с одной стороны и шесть нулей с другой стороны. Поэтому при последовательных сдвигах в тот или иной момент времени эта единица появится либо в шестом, либо в седьмом разряде буферного устройства, причем одновременно две другие ошибки будут располагаться где-то в последних п — Й разрядах.
В случае ошибки в 1-м разряде к содержимому Регистра синдрома прибавляется остаток от деления много~~в~~ Х* 'Х" " на а(Х). Обозначим этот остаток через г;(Х). Тогда для кода Голея исправление ошибок можно провести следующим образом: 1а. Если в синдрома равен 3 или меньше, то рассматриваем синдром как комбинацию ошибок и прибавляем эту комбинацию к членам высших порядков полученного вектора, который содержится в буферном устройстве. 1б. Прибавим к синдрому многочлен гз(Х). Если в результате получится вектор веса 2 или меньше, прибавим синдром к членам высших порядков полученного вектора, который содержится в бу- ферном устройстве, и, кроме того, поменяем на обратный 6-й символ в буфере.
1в. Прибавим к синдрому многочлен ге(Х). Если в результате получится вектор веса 2 или меньше, прибавим синдром к членам высших порядков полученного вектора и, кроме того, поменяем на обратный 7-й символ в буферном устройстве. 2. После сдвига полученного вектора и содержимого регистра синдрома повторяем первый шаг всего 2а раз. Дополнительные разряды, которые должны быть проверены (6-й и 7-й в случае кода Голея), принято называть окнами. Повидимому, не существует простого способа выбора окон, за исключением случая кодов, исправляющих двойные ошибки. Касамн [164) нашел способы их выбора для (31, 16)-кода БЧХ и (63,45)- кода, исправляющих три ошибки, для квадратично-вычстного (41, 21)-кода, исправляющего четыре ошибки, и (31, 11)-кода БЧХ, исправляющего пять ошибок, которые столь же удобны, как и для кода Голея.
В другом варианте метода вылавливания ошибок, известном как перестановочное декодирование 1196), используются сохраняющие код перестановки, отличные от циклических перестановок, (См. равд. 8.11.) Пусть требуется исправить все комбинапии из 1 или меньшего числа ошибок посредством кода с минимальным расстоянием д ) 21+ 1.
Предположим также, что можно найти множество сохраняющих код перестановок Рь Рь ..., Р„таких, что для любой комбинации ч из 1 ошибок по меньшей мере один из векторов ч, чрь чрь ..., чР, содержит й последовательных ошибок. Тогда исправление ошибок можно осуществить следующим образом. Во-первых, применим метод вылавливания ошибок к вектору ч. Если ошибки будут исправлены, то процесс на этом закончится. В противном случае применим этот метод к вектору чРь Если ошибки будут исправлены, получится вектор ч', и тогда искомый вектор будет равен ч'Р~'.
Если этого не произойдет, то применим метод вылавливания ошибок к вектору чР, и т. д. Для того чтобы исправить, например, все комбинации ошибок веса 1 или меньше методом перестаповочного декодирования, необходимо найти совокупность сохраняющих код перестановок, отображающих все комбинации ошибок, которые могут быть исправлены, в комбинации ошибок, содержащие по меньшей мере Й последовательно расположенных правильных символов. Для любого циклического кода имеется несколько различных перестановок, сохраняющих код.
Например, для любого циклического кода с символами из бр(д) перестановки 1 = О, 1, 2, ..., и — 1, (=1,2, ..., отображают каждое кодовое слово в другое кодовое слово при условии, что (а, д) = 1. (См. теорему 8.13.) Для многих кодов можно найти и другие сохраняющие код перестановки. (См., например, разд. 8.11.) Однако, вообще говоря, не известно, как выбрать совокупность перестановок для заданных значений п, й и 1, и даже не известно, сУществУет ли такаЯ совокУпность, Таким образом, хотя перестановочное декодирование применимо к некоторым кодам, ошибки в которых не могут быть исправлены просто методом вылавливания, в настоящее время их применение ограничивается областью относительно коротких кодов или кодов с малыми скоростями передачи.
Возможно также декодировать, используя перестановки, которые не сохраняют кода. Однако при этом декодер должен обладать способностью исправлять комбинации ошибок в используемых эквивалентных кодах. Очевидно, что декодер может исправлять комбинации ошибок в любом коде, если все ошибки находятся в «проверочной» части слов. Иптересяый подход к трудной задаче выбора совокупности перестановок предложен Омурой [227). Результаты проведенных им вычислений показывают, что удивительно малое число случайно выбрапных перестановок дает большую вероятность правильного декодироваяия даже для кодов длиной в несколько сотен символов.
По этому поводу см. задачу 8.24. Известен еще один путь использования метода вылавливания ошибок для исправления несколько большего числа ошибок, чем 1)1г. Однако применение этого метода проб и ошибок, по-видимому, также ограничивается областью относительно коротких кодов. (См. задачу 8.15.) Предположим, что двоичный код может исправлять все комбипации из 1 ошибок, но при этом можно гарантировать, что только 1 — 1 ошибок могут быть циклически сдвинуты в некоторую часть кодового слова, содержащего п — й символов. Любая комбинация веса 1 или меньше эюжет быть исправлена следующим образом. Заменим первый символ слова на обратный и попытаемся декодировать его, используя метод вылавливания ошибок. В этом случае на выходе единственного порогового элемента единица появляется тогда и только тогда, когда 1 — 1 или меньше символов на его входах равны единице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
