У. Питерсон - Коды, исправляющие ошибки (1267328), страница 81
Текст из файла (страница 81)
Отсюда следует, что эти коды, рассматриваемые как коды над 6г" (д'"), асимптотически оптимальны, так же как и коды Бартона. В равд. 11.4 рассматривается корректирующая способность таких кодов для многократных пакетов ошибок. Пример. Код Рида — Соломона с символами из поля 6г (2т) и 1= 4 можно было бы применять для исправления всех пакегов 4 зд (1 1.8) где Р— количество пакетов, а ! — общая длина всех пакетов в комбинаиии, Доказательство. ПУсть В~(Х) и Вх(Х) — две комбинации ошибок соответственно с Р, и Р, пакетами общей длины 1, и !м причем количество нулей внутри пакетов соответственно равняется Х~ и Уь Тогда вес комбинации В,(Х), обозначаемый через ге[В~(Х)], равен 1~ — Я» а вес комбинаций В,(Х) равен 1,— Ль Предположим, что они лежат в одном смежном классе.
Тогда В~(Х) — Вх(Х) является кодовым словом и г! к-. и [В (Х) — В2 (Х)[ = 1~ + !з — У, — Ум (11 9) лины 22 или меньше, если кодовые символы кодиРУютсЯ (-Разными двоичными блоками. Для этого кода потребовалось бы 2 ~ 4 = 8 проверочных блоков или 8 Х 7 = — 56 двоичных символов. длина кода должна равняться 7 Х(2~ — 1) = 889, Код файра длч исправления всех пакетов длины 22 или меньше потребовал бы 38 — 1 = 65 проверочных двоичных символов, Кодовая длина при этом равнялась бы (2" — 1) Х43, или приблизительно 160 млн. двоичных символов.
С другой стороны, пакет длины 8 или меньше двоичных символов затрагивает самое большее два элемента из бр(2'), и поэтому код Рида - Соломона мог бы исправить любые два пакета длины 8 или меньше. Он мог бы исправить до четырех пакетов, если бы каждый из них приходился на один элемент из поля 6Р(2т), Из равенства (11.7) следует, что существует (3556,3500)-код Бартона, для которого Ь = — 22 и г = 12. Заметим, что этот код обладает такой же корректирующей способностью для пакетов н имеет то же самое число проверочных символов, что и код Рида— Соломона, но в 4 раза длиннее. Однако он не может исправлять многократные пакеты.
БХЧ-коды могут быть реализованы с помощью методов, опи. санных в гл. 9. Кроме того, если достаточно исправлять только одиночные пакеты, то можно использовать метод, описанный в равд. 11.3, при котором требуется меньше оборудования. Дополнительные корректирующие возможности кода можно использовать для обнаружения ошибок (любая комбинация ошибок, которая могла бы быть исправлена, если полностью используется корректирующая способность кода, конечно, может быть обнаружена) или для исправления пакетов, которое не гарантируется корректирующей способностью кода. (См.
равд. 11.3.) Теорема 11.4. Если код с минимальным расстоянием г! применяется для исправления многократных пакетов ошибок, то он исправляет все комбинации пакетов, удовлетворяюи!ие условию Если В~ (Х) и Вз (Х) лежат в одном смежном классе, то (1+ Х)(В~(Х) — Вр(Х)] = (1+ Х)В,(Х) — (1+Х)В (Х) является кодовым словом и (1+Х)В~(Х) и (1+ Х)Вх(Х) тоже лежат в одном смежном классе. Вес (1 -1- Х) В,(Х) не превышает числа 2(Р~+Х~), а вес (1+Х)В~(Х) не превышает числа 2(Рз+ЯД, Поэтому Н:~.,ш((1+Х)(В,(Х) — Вз(Х)))~(2(Р, +Р,+Х, +Ят). (11.10) Прибавляя дважды выражение(11.9) к(11.
10), получим 3~~ «» 2 (1! + 12 + 1 ! + Рт)' (! 1.1 1) Так как для произвольных двух пакетов, удовлетворяющих соотношению (11.8), неравенство (1!.11) не выполняется, то выбранные пакеты лежат в разных смежных классах. Таким образом, совокупность пакетов, удовлетворяющих условию (1!.8), может быть исп авлена.
Ч. т. д. ели Р = 1, то теорема 11.4 гарантирует, что циклический код с минимальным расстоянием и' исправляет пакеты длины Ь, если за — 8 Ь) Этот результат показывает, что код, исправляющий случайные ошибки, можно применять для исправления как случайных ошибок, так и пакетов ошибок, но не для исправления одновременно тех и других, т. е. смежные классы, содержащие комбинации случайных ошибок, которые могут быть исправлены, не обязательно отличаются от смежных классов, содержащих пакеты. Коды, исправляющие ошибки обоих видов, рассматриваются в равд. 11.5. 11.2. Некоторые хорошие коды, исправляющие пакеты ошибок, построенные с помощью ЭВМ Коды, представленные в этом разделе, взяты нз списка, составленного несколькими авторами (170, 190, 339) Для каждого значения скорости передачи приводится циклический или укороченный циклический код с наибольшим известным отношением Ь/и.
Если два или большее количество кодов имеют одно и то же значение Ь/и, то приводится самый короткий. Перемежая коды из табл. 11.1, можно построить коды произвольной длины с указанными скоростью и отношением Ь/и. Очевидно, что другие скорости можно получить при укорочении кодов с несколько большей скоростью. Длинные коды Бартона имеют несколько большие возможности при исправлении пакетов, чем коды, приведенные здесь при /1 =:- 0,68. (См, задачу 11.4.) 11.8. Декодирование циклические коды, исправляющие пакеты, можно декодировать с помощью очень простого варианта вылавливающего ошибки декодера, который описан в разя.
8.9. В этом разделе рассматривался код, исправляющий ! случайных ошибок, и предполагалось, „о имеет место комбинация ошибок, в которой все ! или меньшее количество ошибок расположены в и — А старших разрядах кода. Выло показано, что сдвинутый синдром, вычисленный при помощи схемы, изображенной на фиг. 8.5, ограничен а — й старшими разрядами ошибочной комбинации.
Вообще, если в комбинации ошибок, которая может быть исправлена, все ошибки расположены в и — Й старших разрядах, то сдвинутый синдром совпадает с этими л — й ошибочными цифрами старшего порядка. Это можно показать следующим образом. Предположим, что многочлен ошибок имеет вид е (Х) = Х~( (Х), где !(Х) — многочлен степени п — lг — 1 или меньше. Схема, представленная на фиг. 8.5, умножает синдром принятого слова на Х"-". Таким образом, она вычисляет синдром Х"-"е(Х) = = !(Х)шобХ" — 1. Но поскольку степень ((Х) равна а — А — 1 и порождающий многочлен кода имеет степень п — А, то синдром равен ((Х). Этот результат позволяет декодировать циклический (и, й)-код с корректирующей способностью для пакетов Ь при помощи схемы, приведенной на фиг.
11.1. (Ниже предполагается, что код двоичный. Для обобщения на д-ичные коды нужно только дополнительно определить соответствующие д-ичные логические элементы на фиг. 11.!.) Предположим, что появился пакет ошибок длины Ь или меньше. Эта схема вычисляет сдвинутый вариант синдрома комбинации ошибок, которая содержится в принятом слове.
Если пакет ограничен Ь старшими разрядами принятого слова, то в Ь справа расположенных ячейках генератора синдрома находится пакет ошибок и в силу соображений, приведенных в предыдущем разделе, п — й — Ь ячеек слева будут содержать нули. Логический элемент «ИЛИ» обнаруживает эту ситуацию; поскольку его выходной символ при этом равен О, обратная связь генератора синдрома открыта, а вход в двоичный сумматор закрыт. По мере сдвига генератора синдрома и буферного регистра синдром, который является пакетом ошибок, складывается с принятым словом, тем самым исправляя его. Если бы пакет был расположен в другом месте слова, то мог бы быть исправлен таким же путем.
После сдвига пакет займет Ь старших ячеек буфера. В то же время Ь символов синдрома стар" щего порядка будут совпадать, как и прежде, с пакетом. Фиг. 11.1. лгекодер циклического кода, исправляющего пакеты ощиоок. Этот способ декодирования не позволяет исправлять кпакеты», расположенные в 1 старших и Ь вЂ” 1 младших разрядах слова. Такие пакеты, однако, в принципе могут быть исправлены циклическим кодом, исправляющим пакеты длины Ь. Это можно сделать даже проще, если применить генератор синдрома без предварительного умножения на Х" К (См. задачу 11.Ц Пример. Многочлен д(Х) =(Х'+ Хе+ 1)(Х'+ 1) =(Х" + Хи + Х'-+ Х'+ Х'+ 1) порождает двоичный код Файра длины п = 9(2а — !) = 279, который исправляет произвольный одиночный пакет длины 5 или меньше. Он имеет 14 проверочных символов и 279 — 14 = 265 информационных символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
