У. Питерсон - Коды, исправляющие ошибки (1267328), страница 83
Текст из файла (страница 83)
Замечания Первым циклическим кодом, исправляющим пакеты ошибок, был код Эйбрамсона [1, 6]. Этот код, исправляющий одиночные ошибки и две соседние ошибки, явился отправной точкой для всех последующих работ по циклическим кодам, исправляющим пакеты ошибок. Файр [84] нашел важный класс кодов при попытке обобщить работу Эйбрамсоиа. Дальнейшие результаты были получены Меласом [218], Рейгером [252], Касами [162], Элспасом и Шортом [76], Меласом и Горогом [220], Бартоном [35]. Большинство из приведенных в табл.
11.1 циклических и укооченных циклических кодов найдено при помощи ЭВМ Касами 164] и Касами и Матоба [170]. Процедура исправления всех пакетов длины, не превышающей Ь, предложена Питерсоном [234], однако по существу она представляет собой усовершенствование методов Эйбрамсона [1], Эйбрамсона и Элспаса [6] и Меггита [217]. (См. равд. 8.9.) Г1роцедура исправления пакетов длины, большей чем 6 и меньшей чем и — А, описана Галлагером.
Коды Стоуна [290], исправляющие многократные пакеты ошибок, близко связаны с кодами Рида--Соломона. Однако последние обычно оказываются лучше при исправлении многократных пакетов. Теорема 11.6 доказана Стоуном [290], хотя вариант, приведенный здесь, принадлежит Товарссу и Шива [299]. Задачи 11 1 Покажите, что для любых и и 6 существует циклический код длины и, способный исправить любой одиночный пакет стираний длины 6 или меньше, для которого требуется 6 проверочных символов.
(Ср. с задачей 4.1.) 11.2. Приведенный ниже элементарный код-произведение по- дезен при исправлении ошибок, Символы кода располагаются в виде прямоугольной таблицы ХпХ Х Х,Х Хж Хм Хзз Хм Хм Х„ Х„ Хм Хм Хзз Хм Х„Хм Х,д Хм Хж Хм Хзз Хм Хм Х, Х Х Х, Хзз Удовлетворяются следующие проверочные соотношения: Х Хм — — 0 — проверка по столбцам, ! К Хн — — 0 — проверка по диагоналям. Символы передаются строка за строкой, слева направо и сверху вниз. Это построение можно обобщить на случай кода, задаваемого таблицей из т столбцов и т+ 1 строк с 2т+ 1 проверочными соотношениями.
а. Покажите, что имеется только 2т независимых проверочных соотношений. б. Путем элементарных геометрических рассуждений покажите, что этот код может исправлять любой одиночный пакет ошибок длины 6 или меньше, если т ) 26 — !. в. Покажите, что это циклический код, порождаемый много- членом (Х™ — !) (Х'"+' — 1)/(Х вЂ” 1), и постройте схему для кодирования. г. Дайте алгебраическое доказательство того„ что этот код бу.
дет исправлять любой одиночный пакет ошибок длины Ь или меньше, если и ) 26 — 1. 11.3. Постройте декодер, аналогичный описанному в разд. 1!.3, которым можно исправлять пакеты, перекрывающие концы принятых слов. (Указание: используйте генератор синдрома без предварительного умножения на Х вЂ ".) 11.4. Покажите, что двоичный код, исправляющий пакеты с параметрами и = 2040, !! = 0,90 Ь = 85, можно построить, используя коды из табл.
11.!. Покажите, далее, что существует код Рида — Соломона той же длины и приблизительно с той же скоростью, для которого Ь = 97. 11.5. Постройте код Бартона с параметрами (п — А)=208 и Ь = 97. Сравните с кодом Рида — Соломона из предыдущего примера. 11.6. Известно, что укороченный циклический код, порожденный многочленом (Х' — !.)да(Х), имеет минимальное расстояние 21 ! 2 и способен исправлять пакеты длины Ь. Докажите, что код манжет исправлять любую комбинацию случайных ошибок веса, большего чем 1, и любой пакет длины, равной пнп(с,Ь). (Укан„е: докажите, что любая комбинация веса ! илн меньше и любой пакет длины, равной пнп(с, Ь), не могут быть в одном смежном классе.) 11.7. Двоичный код максимальной длины с длиной слов, равной 15, порождается многочленом 7531 (первымн идут цифры высшего порядка, запись восьмеричная).
Покажите, что этот код, кроме всех комбинаций веса 3 или меньше, может также исправлять все пакеты длины 5 или меньше. Для кода длины 31, порожденного многочленом 535437 ! 51, определите величину Ь, предполагая, что код способен исправлять 7 случайных ошибок. 11.8. Проверьте равенства (1!.12) и (11.13). 11.й !1). Покажите, что для циклического (2'" — 1, 2'" — т — 2)- кода Хэмминга Ь = 2. 11.10.
Пусть гх — корень неприводимого многочлена р(Х) степени Ь, и пусть С вЂ” код с символами из 17Е(дь), порожденный многочленом д(Х) = (Х вЂ” 1) (Х вЂ” аь). Покажите, что если каждый символ в коде С заменить его обычным представлением в виде Ь-мерного вектора над 6Р(д), то полученный в результате код будет кодом Бартона. 12 Синхронизация блоковых кодов Для того чтобы декодировать блоковый код, декодер должен уметь различать информационные и проверочные символы или, что эквивалентно, определять первый символ принятого слова.
В некоторых каналах символы могут вставляться в слово нли выпадать из него. Это приводит к тому, что декодер неправильно определяет-границы этого и последующих слов. В этой главе рассматриваются вопросы, связанные с построением блоковых кодов, способных восстанавливать синхронизацию после вставки нли выпадения одного илн большего количества символов. Всюду рассматривается д-ичный случай. Синхронизация может быть обычно восстановлена методом проб и ошибок.
В типичном случае неправильное определение границ принятого слова приводит к тому, что оно резко отличается от любого кодового слова. В таких ситуациях декодер может интерпретировать длинную последовательность принятых слов, которые содержат необычно много ошибок, как потерю синхронизации. Проверка всех и возможных позиций для начала и конца слова приводит в конечном счете к восстановлению синхронизации'). Хотя эта схема не требует введения дополнительной избыточности, может произойти значительное количество ошибок декодирования, прежде чем восстановится синхронизация.
В этом смысле методы синхронизации, описанные в этой главе, лучше метода проб н ошибок. Когда слово сдвинуто, восстановить синхронизацию значительно проще, чем в случае, когда символы добавлены к слову нли выпали из него. Таким образом, в большинстве методов синхронизации используются слово или слова, следующие за тем, в кото. ром произошел сбой синхронизации, а не непосредственно иска.
женное слово. Исправление комбинаций ошибок, которые являются результатом вставки или выпадения символов, т. е. исправление оигибок синхронизации, вообще говоря, довольно трудная задача 13081 и обычно не такая важная, как задача восстановления синхронизации. Коды, исправляющие ошибки синхронизации, в этой книге не рассматриваются. Всегда возможно, что аддитивные ошибки образуют комбинацию, которая представляется декодеру как результат синхроннза- ') Эта процедура моисет быть весьма эффективна для сверточных кодов ибо тогда для сннхрониэации требуется провести выбор лишь среди пэ позиция „„онного сдвига.
После ошибочного решения о «синхронизации» кодер обычно восстанавливает синхронизацию в следующем е, Однако вероятность такого неправильного решения можно уменг шить, если протребовать, чтобы зто решение принималось лишь тогда, когда несколько последовательно принятых слов согласованно указывают на сбой синхронизации. В синхронизируемых системах передачи данных незначительные сдвиги на один или несколько символов встречаются чаще, чем сдвиги на большое число символов. Поэтому коды, обсуждаемые в этой главе, построейы для исправления или обнаружения сдвигов не больше чем на некоторое фиксированное количество символов. Проблема установления синхронизации без каких-либо предварительных знаний о правильном расположении слова, возникаюшзя, например, в начале передачи, здесь подробно не обсуждается.
далее в этой главе используется следующая терминология. Потеря синхронизш1ии в з символов происходит, когда счетчик принятых символов теряет з тактов. Аналогично сиихронизапионный избыток имеет место, когда счетчик насчитывает больше символов, чем их должно быть. Классический метод восстановления синхронизации в системах передачи данных требует использования специальных синхронизируюших символов, которые вставляются между кодовыми словами 1напрнмер, буква пробела в коде Морзе). Очевидно, для двоичных систем невозможно выделить один из символов на синхронизацию, и поэтому этот префикс обычно выбирается так, чтобы он образовывал последовательность двоичных символов с пикообразной автокорреляционной функцией, т.
е. последовательность Беркера 113]. Восстановление синхронизации при помощи таких последовательностей может быть эффективным, если в последовательности имеется относительно мало аддитивных ошибок. Предпочтительнее рассматривать вместе аддитивные ошибки и ошибки синхронизации и строить коды, которые могут их исправлять единым способом, чем вводить отдельный префикс только для целей синхронизации. Такие коды и являются предметом обсуждения я этой главе. Рассматриваются три класса кодов: !. Коды, которые могут обнаруживать или исправлять потерю синхронизации, но не аддитивные ошибки.
2. Коды, которые могут исправлять и потерю синхронизации, и аддитивные ошибки при условии, что они не происходят одновременно. 3. Коды, которые могут исправлять как сбой синхронизации, так и аддитивные ошибки, даже если они происходят одновременно. Понятие степени свободы от запятой вводится кратко в равд. 12.1; этот термин используется в наиболее общих исследова.
киях по восстановлению синхронизации. Коды„ связанные с хоро- шими линейными кодамн, легче реализуются при практическом применении, наиболее привлекательные из них обсуждаются в следующих разделах. 12Л. Коды, которые только восстанавливают синхронизацию В этом разделе предполагается, что не происходит аддитивных ошибок. Рассматриваются только блоковые коды с фиксированной длиной. Коды с переменной длиной кодовых слов исследова. лись, но изложение этих вопросов лежит вне рамок этой книги [107, 269].
Готорят, что код имеет степень свободы от запятой г, если для каждой пары кодовых слов а= [а„-и .,аьаь1 и Ь = [Ь -ь-., ..., Ьь Ьь) наборы длины и [а„; „..., а„Ь„ь ..., Ь„,.1 н [а; „... ..., аь, Ь„ь..., Ь,1 прн 0(1 - г не являются кодовыми словами, Кодовые слова а и Ь не обязательно различны. Если слово а передается раньше слова Ь и декодер пытается декодировать слово а, то первый из этих наборов длины и возникает при потере синхронизации в 1 символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
