У. Питерсон - Коды, исправляющие ошибки (1267328), страница 34
Текст из файла (страница 34)
На фиг. 5.4 изображена общая система каскадного кодирования. Первый код, называемый внутренним, представляет собой (п,й)-код с символами из поля 6Г(д). Второй код, называемый внешним, является (Ф,К)-кодом с символами из 6Р(ф). Кодирование осуществляется следующим образом." 1) Блок из АК информационных символов делится иа К «подблоков» по й символов. 2) Каждый подблок из А символов рассматривается как символ над 6г'(д"). Затем К подблоков кодируются кодовыми словами внешнего кода, составленными из У подблоков.
3) Каждый из йг подблоков, содержащий А символов, кодируется как А информационных символов кодового слова длины и во внутреннем коде. Таким образом, совокупность 1Ч кодовых слов внутреннего (п,й)-кода является кодовым словом каскадного (йгп, Кй)-кода. Способ декодирования очевиден. Сначала производится декодирование внутреннего кода, в результате которого У слов внутреннего кода сводятся к У подблокам по А символов. Затем эти У подблоков декодируются в К подблоков с помощью метода декодирования, используемого для внешнего кода.
Легко охарактеризовать возможности каскадного кода исправлять ошибки: неисправленная ошибка будет появляться в том случае, если неисправленная комбинация слов внутреннего кода будет также неисправленной комбинацией и для внешнего кода. Обычно в качестве внутреннего кода выбирается двоичный (и,А)-код, а в качестве внешнего в код Рида — Соломона или укороченный код Рида в Соломона с символами из 6г(2"), (См.
Вмешмий Внутренний мадер ф/фсад [ Внумревний днкадер ~п,КЬ- д) над Нг(а'и д-иннмй канал декадер [, Щк)-над ) вад Ыкр)")/ кодер н,к)- д) ад ВР(йк)7 ,Рис, а.е. КаНаЛ СВЯЗИ, И КОТОРОМ ИСПОЛЬЗУЕТСЯ КаСКаДНЫй КОД. гл 9.) ФоРпи [91] пРовел шиРокое исследование каскадных кодов, изучая вопрос о выборе внутреннего и внешнего кодов и возможные вероятности ошибки. В частности„ он показал, что для двоичного симметричного канала при любой скорости передачи )г, не превосходящей пропускной способности канала, и при лтобом выборе числа и существует каскадный код со скоростью передачи, равной по меньшей мере тс, и с вероятностью ошибки, не превосходящей е.
Пример. В качестве внутреннего кода может быть использован двоичный (7,4)-код Хэмминга, исправляющий одиночные ошибки. (15,7)-код Рида — Соломона с символами из 6Г(2') исправляет любую комбинацию из четырех или меньшего числа ошибок. Каждый символ из 6Р(24) может быть представлен в виде четырех двоичных символов (см. табл. 5.1). Для этого кода 28 информационных символов разделяется на семь подблоков по четыре двоичных символа каждый.
Затем каждый из подблоков кодируется как слово (7,4)-кода Хэмминга. Таким образом, получается код, каждое кодовое слово которого содержит 105 двоичных символов, 28 из которых являются информационными. Кодовое слово будет правильно декодировано тогда и только тогда, когда не более четырех слов внутреннего (7,4)-кода содержат более чем одну ошибку. Замечания Коды Хэмминга впервые описаны в работе Хэмминга [138].
Обобщения на случай недвоичного кода сделаны Голеем [115, 116] и, наконец, на случай, когда символы принимают значения в произвольном конечном поле,— Коком [53]. См. также работы Слепяна [278] и Заремба [338] и материал по кодам Хэмминга в гл.
8. (23, 12)-код Голея описан в работе Голея [114]; в качестве циклического кода он изучался Прейнджем [243, 245]. Митани [221] построил коды Рида [249] — Маллера [225]; способ декодирования, рассмотренный в разд. 5.5, предложен Ридом. Эти коды были построены другим способом в работе Хонда [143]; еще одно их описание приведено в работах Слепяна [277, 278]. Геомет. Рическая трактовка кодов Рида — Маллера и некоторых других кодов была впервые дана в хорошо написанном и интересном докладе Кауца [172). Дворк и Хеллер [55) получили обобщение, идущее дальше простого использования другого поля; более естественное обобщение приводится в гл.
10. Коды, получаемые с помощью матриц Адамара, впервые были найдены Плоткиным [242). Связь их с матрицами Адамара и с симметричными блоковыми планами была указана Боувом н Шрикханде [ЗЦ. [См. также работу Хармута [!39).) Материал относительно произведений кодов заимствован преимущественно из работы Элайеса [87). Некоторый дополнительный материал появился в работах [5, 37, 39, 2ЗЦ. Недавно Уэлдон [328) и Редди и Робинсон [248) разработали метод декодирования произведения кодов, при котором простым способом используются декодеры для составляющих кодов.
Берлекэмп [2Ц несколько расширил область применения безошибочного кодирования Элайеса. Задача 5.3 является обобщением предложения 5 Слепяна [277, 2781. Теоретикографовые коды впервые изучались Касами [15Ц, а позднее— Хаффменом [1491 и фрейзером [961 Работы Галлагера по теории низкоплотностных кодов изданы в виде монографии [102). Задачи 5.1. Пусть Н вЂ” матрица размерности т к,' и, где 2 — ' ( и ( 2"', столбцы которой являются двоичным представлением их' номеров. Покажите, что для кода, который является нулевым пространством матрицы Н, каждый смежный класс содержит вектор веса 2 или меньше.
Покажите, что этот код исправляет все одиночные ошибки и, следовательно, квазисовершенен. (Указание: используйте задачу 3.2.) 5.2. Покажите, что двоичный код Хэмминга, исправляющий одну и обнаруживающий две ошибки, является квазисовершенным, если он имеет длину и = 2~ и и+ 1 проверочных символов, ио что если из проверочной матрицы отбросить любой столбец, то появится смежный класс с минимальным весом 3. 5.3.
Покажите, что существует квазисовершенный исправляющий одиночные ошибки двоичный код с т проверочными символами и любой длиной и, удовлетворяющий неравенству 2<'"и+'— — 2 ( и < 2, если и четно, и 2("+'ха+ 2аа — 'да — 2 ( п < 2'", если т нечетно. [Указание: включите в проверочную матрицу все столбцы, которые содержат нули в верхней половине строк, и все столбцы, которые содержат нули в нижней половине строк.) Этот результат может быть обобщен непосредственно на линейные коды с д символами. 5.4. Укажите процедуру для исправления двух стираний для кода Хэмминга с расстоянием, равным 3. 5,5.
Укажите способ декодирования, исправляющий 2 ' — 1 стираний для кода Рида — Маллера. 5.8. Покажите„что простейший код-произведение, использующий одну проверку на четность по строкам и одну проверку на четность по столбцам, может исправлять все комбинации из трех стираний, но что существуют неисправимые комбинации из четырех стираний.
5.7. Покажите, что все кодовые слова из нулевого пространства двоичного кода Хэмминга, исправляющего одиночные ошибки, имеют один и тот же вес, и затем, используя тождества МакУильямс, покажите, что производящая функция для распределения весов в коде Хэммннга имеет внд й() = „+, Й1+ )" +.(1+.)'"-'"'(1 —.)"'в 1. 5.8. Покажите, что распределение весов для двоичного кода Хэмминга длины и = 2 — 1 с минимальным расстоянием, равным 4, имеет вид [,(х) = — [(1+ к)" + (1 — х)" + 2(п — Ц(1 — хт)'чз [.
(Это можно доказать, либо вычисляя распределение весов для двойственного кода и используя тождества Мак-Уильямс, либо непосредственно пользуясь выражением для ~з(х) из задачи 5.7.) 5.9. Результаты задач 5.7 и 5.8 можно использовать при выводе выражения вероятности необнаружения ошибки для кода Хэмминга, который используется только для обнаружения ошибок при передаче по ДСК. Покажите, что Р (необнаруженне ошибки) =Я" '[7" ( — ) — 1~, где Р— вероятность ошибки в ДСК, Я = 1 — Р, а 7(Х) — функции, найденные в предыдущих задачах. 5.10. Докажите, что все кодовые слова кода, двойственного к обобщенному коду Хэммннга, нмеют один н тот же вес„а затем на основе тождеств Мак-Уильямс покажите, что производящая функция для распределения весов обобщенного кода Хэмминга имеет вид 1(Х)=, ([1+(д — 1)хГ+ +„(9 Ц[1+(Ч вЂ” 1) 1'""'"(1 — )м" и""').
511. Покажите, что символы любого произведения кодов могут быть переставлены так, чтобы получился код, у которого Ь~)шах(Ь,па+ 1„Ьзп, + 1,). 5.12. Некоторые авторы рассматривали двойственные коды для произведения кодов. Покажите, что если через д, и 6з обозначены соответственно минимальные расстояния двойственных кодов для кодов-строк и кодов-столбцов, а Ы вЂ” минимальное расстояние двойственного кода для произведения кодов, то й = ппп (д„й,). 5.13.
Нижняя строка порождающей матрицы линейного двоичного (15„7) -кода имеет вид (000000!101!000!). Этот код обладает тем свойством, что циклический сдвиг кодового слова (в любом направлении) является другим кодовым словом, т. е. если ими~э ° ° ° ио есть кодовое слово, то ама,з ... азам тоже является кодовым словом. Постройте порождавшую матрицу для этого кода в прнведенно-ступенчатой форме. Этот код является примером циклического кода. Изучению этих кодов посвящены главы 6 — 12. 5.14.
Для заданных (иьй)-кода с минимальным расстоянием д~ н (амй)-кода с минимальным расстоянием Нз постройте (а~+ + пм Й) -код с минимальным расстоянием по меньшей мере б, + г(ь 5.15 [110). Предполагается, что сушествует (л, й)-код с минимальным расстоянием г(, двойственный код к которому имеет минимальное расстояние д. Докажите, что этот код содержит в качестве собственного подпространства (и — д, й — д + 1)-код с минимальным расстоянием д. 5.16. Используя результат предыдушей задачи н сведении о двоичном циклическом коде длины 31, приведенные в приложении Г, постройте (26, 6)-код с г( = 12. (Ср. с табл.
5.4.) 5.!7. Универсальная цифровая вычислительная машина, в памяти которой содержится 4096 слов, состояших из 12 разрядов, используется для декодирования кода Голея. Имеется команда осушествления операции «исключаюшего ИЛИ» для полного слова, причем время, необходимое для выполнения каждой из команд, равно 1 мкс. Составьте программу обраи1сния к таблице для декодирования этого кода. Определите наибольшую скорость, с которой этот декодер может обрабатывать информацию, б.18, Рассмотрите класс кодов, элементами которого являются произведения кодов на самих себя. Покажите, что прн больших значениях л отношение д/и должно лежать ниже границы Гилберта. Обобщите это на случай произведения двух различных кодов.
(Этот результат означает, что длинные коды-произведения имеют относительно малое минимальное расстояние.) 6.19. Подтвердите возможность существования совершенного (11,6)-кода над ОЕ(3), исправляющего двойные ошибки. (Действительно, такой код существует и был построен Голеем [!141.) Определите Аз — число кодовых слов минимального веса. 6 Кольца многочленов и поля Галуа В большей части последующих глав этой книги предполагается некоторое знакомство с понятиями колец, идеалов, классов вычетов и с основами структуры конечных полей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
