У. Питерсон - Коды, исправляющие ошибки (1267328), страница 30
Текст из файла (страница 30)
Во втором случае типичная процедура состояла в том, чтобы получить по возможности хороший код, вложив в это разумное количество труда, а затем сравнить его со всеми другими кодами. Даже с полным учетом современного уровня знаний по теории кодирования решение этой задачи остается очень трудоемким и утомительным даже для коротких кодов 188, 277) Так как совокупность весов, совокупность чисел, задающих модулярное представление, и совокупность величин ои (количества образующих смежных классов веса 1) очень тесно связаны друг с другом. то, естественно, возникает соблазн высказать об их связях различные гипотезы.
К подобным гипотезам найдено некоторое число противоречащих примеров. Например, построены два кода, имеющие одну и гу же совокупность весов кодовых слов, но различные совокупности чисел, задающих их модулярные представления, и различные совокупности величин аь Комбинации условий, для которых найдены противоречащие примеры, перечислены в табл. 5,3. Более подробные сведения можно найти в работе [88). Таблица 5.2. Величины (и, й) для известных нетривиальных оптимальных групповых кодов лля двоичного симметричного канала прн па 31.
Некоторые более длинные коды перечислены в работах ([316, 317!) (ниже 1 — наибольшее число, такое, что все комбинации из Г или меньшего числа ошибок являются обРазУю. шими смежных классов) Квазисовершенные коды Самана 1л. Ь) Ссылка 2777 2777 2777 ~а а [881 [88! Прейндж (частноае сообщение) [3161 (З17! [881 Другие коды ("! [в~ 2777 277 2 77 2777 277 277 277 277~ [2771 [277! [881 ~88! 6 [881 [300~ [881 [3001 [300~ [ВСО) [3001 [31 (1О, 5) (11, 4) (14, 6) 11, 6) (14, 8) (15. 9) (17, 9) (19.
10) (20, 11) (21, 12) (21, 14) (7, 2) (8, 3) (9, 2) (9, 3) (10',2) (1 ~3)) (1О, 4) (1 1, 2) (1 1, 5) 11, 3) (12, 2) (12, 3) (12, 4) ~12, 5~ (13, 4) (13, 5) (13, 6) (13, 7) (14, 2) (22, 12) (22, 13) (22, 15) (23, 12) (23, 14) 23, 16) 24, 12) (25, 12) (25, 15) (26, 16) (27, 17) (28, 18) (29, 19) (30, 20) (31, 20) (14, 3) (14, 4) (14, 5) (15, 2) (15, 3) (1К 4) (15, 5) ! 16, 2) 16, 3) 16, 4) (16, 5) 16, 8) 17, 2) (17, 3) (17, 6) М2) (18, 3) (1В, 7) (19, 8) (22, 11) [881 [3161 [881 [1151 [316) !881 [[151 [316! [317[ таалииа 6.6. ПРотиворечаЩие примеры к типичным гипотезам Совокупности чисел, еаиаюнме мсдуаярное нредставаение Сове!суниостн вссов кодовых слов Совокупности величии а Замечания (н, М Различные Одинаковые Различные Одинаковые Неоптимальные Оптимальные Неоптимальные Оптимальные Одинаковые Различные Различные Одинаковые Одинаковые Различные Одинаковые Различные Одинаковые Различные (16, 3) (14,' З~ (14, 6) (14, 6) Интересно также отметить, что во всех известных случаях, кроме (15,3)-кода, один и тот же код оптимален для всех значений вероятности ошибки в канале Р, меньших '/з.
Прн менее сильном определении оптимальности Боуз н Кеблер (28) смогли несколько продвинуться в поисках оптимальных кодов. Они считали оптимальным код с наибольшим возможным значением т, который исправляет все ошибки веса т илн меныпе и наибольшее возможное число ошибок веса лт+ 1. 5.4. Двоичные коды с большим минимальным расстоянием Трудности, возникающие при поисках оптимальных кодов, подсказывают, что, возможно, более плодотворными могут оказаться поиски не обязательно оптимальных, но хотя бы просто хороших кодов. По такому пути пошли несколько авторов, и в этом разделе сведены в таблицу некоторые результаты этих поисков. Под хорошим кодом здесь будет подразумеваться такой код, который обладает наибольшим числом информационных символов при фиксированных значениях длины кода и минимального расстояния.
В табл. 5.4 перечислены двоичные линейные коды этого типа для и (31 и и(( 14. Разумеется, этой таблицей можно также пользоваться для определения наибольшей известной величины з( прн заданных значениях и и А. При п < 24 или И< 6 различные границы для минимального расстояния показывают, что все перечисленные коды являются наилучшими в том смысле, что невозможно найти код с теми же самыми значениями п и е(, для которого Ф больше. При и ) 25 и з( ~ 7 коды, отмеченные звездочкой, также являются наилучшими. (См. работы (40, 300, 3!4, 316, 317].) Каждый код в таблице снабжен индексом (отсутствие индекса тоже имеет свой смысл). Эти индексы вместе с приведенным под таблицей разъяснением их смысла позволяют построить любой нз перечисленных выше кодош Габлица 5.4.
Перечень наибольших нелестных значений й при захаииых а н и' 3 1 Б б 2 6 3 2 7 4в 3.4 8 4 4Б 9 5 4 10 6 5 11 7 6 12 8 7 13 9 8 14 10 9 15 11 104 16 11 11Б 17 12 11 2в 20 3 28 2 3Б 4я бв 5 3 4 1 1 1 1 1 1 1 1 1 1 20 2Р 2 2 3 3 В 8 бв 5 2 20 2 8д 9, 9 9В 9 2 20 2 18 13 12 19 14 13 20 15 14 вв 3 10 11 1О з!л з 4 5 з з 9 ю ы 12 13 !4 Зв 5 )О 9 6 6 6 68 6)у 6 10 21 16 15 22 17 16 23 )8 17 24 19 18 25 20 19 26 21 20 27 22 21 28 23 22 29 24 23 30 25 24 31 26„ 25А )В ИА 13 12 !4 [ЗВ 14 148 15 14 16 15 17 16 18 17 19 18 20 19 2[в 20А И )О 120 И 128 12 12 " 1 13, 12 14 13 14, 14 " 0 1511 14 160 150* 16 16К И 10 9 И, И 10 Иу 1)в Зв 2! 2Р 3 2, 2, 4 24 2 5 3 2, 5," 3 3 6 4 3 6 5' 4а 7 5 5 8 6 е 5 60" 101 6) 64 Здесь мспсльаованы следующие обоэивчвния: Иэаесщо.
что этот код наилучший! отсутствие инжаего нндеКса-укороченный вариант кода, расположенного ныне; А-код. полученный отбрасыванием всех кодовых слов нечетного веса иэ кода. расположенного левее:  — кол Воуэа — Чоулхури — Хоквиигема) С-Калайи н 9)нрваагнес [401; О-кал, полученный отбрасыванием проверочного символа нв кода, расположенного правее н виже; Б-кол. полученный лобавлевнем общей проверки иа четность к коду, расположенному левее н выпм' Р Фонтейн и Питерсов [885 О код Голам Н-код Хэмминга; 1-код. полученный лобавленнем Фиктивных проверочных симеонов к коду, расположеиаому ньиве: К-Карпин [1091! й) аол Макдональда [191.
19211 Р- Прейвдж [частное сообщение): 0- ксажщиклический ксп [42)1 з — сэюпви [кп))! )У вЂ” Вагнер [814) н Калайи и 8[нрваэгиьс 14Щ: Е-Геталс 11091 [см задачу Д18) и Калайи н й)лрваагиес [401. 5.6. Коды Рида — Маллера Коды Рида — Маллера образуют класс двоичных групповых кодов, существующих в широкой области значений скоростей передачи и минимальных расстояний. Фактически эти коды эквивалентны циклическим кодам с дополнительной проверкой на четность по всем символам.
Они являются основой для мажоритарнодекадируемых кодов, рассматриваемых в гл. 10. Для любых пт и г~ и существует код Рида — Маллера, для которого и = 2 , Ь=1+С' + ... +С', а — Ь=1+С' + ... +С 0=2~ '=Минимальный вес. (5.2) Построение этих кодов не требует применения большого мате- матического аппарата. Рассмотрим следующую совокупность век- торов над полем из двух элементов. Пусть ча†вектор длины 2', все компоненты которого равны 1, а чьчм ..., ч — строки мат- рицы, столбцами которой являются все возможные двоичнгяе на- боры длины и. (См.
фиг. Б.! для т = 4.) Определим следующим образом векторное произведение двух векторов: а=(а„ав, ..., а„), '$~=(Ь~» Ьм ° ° ° » Ьл) пч=(а,Ьь аА„..., а„Ь„). При таком определении векторы образуют коммутативную линейную ассоциативную алгебру. Рассмотрим, наконец, совокупность векторов, образованную произведениями векторов чь взятых по Интересно отметить, что в нескольких случаях можно построить нелинейный код с большим числом кодовых слов, чем у наилучшего линейного кода при тех же самых значениях а и»4. Слоуэн (28Ц построил класс нелинейных двоичных кодов, исправляющих одиночные ошибки, которые содержат больше кодовых слов, чем соответствующий наилучший линейный код. Препарата (247), обобщая работы Грина (128) и Нордстрома и Робинсона (226], построил класс систематических нелинейных кодов, исправляющих две ошибки, с наибольшим возможным числом кодовых слов. Эти коды тесно связаны с циклическими кодами, и кодирование может производиться с помощью нелинейного регистра сдвига с обратной связью.
Для них была также разработана процедура декодирования. чо = (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) ча=-(0000000011 11 1 111) ъса=(0000111100001111) кт = (О 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1) ч, = (О 1 О 1 О 1 О 1 О 1 О 1 О 1 О 1) УаЪГ3 (О 0 0 0 0 0 0 0 0 0 О 0 1 1 1 1 ) ъгаъст (О 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1) ъатг1 (0000000001010101) ъаъв=(0000001100000011) ъч ч, = (О 0 О 0 О 1 0 1 0 0 0 0 0 1 0 1) тгвта=(0001000100010001) чаУЗЪт (000000000000001 1) врач, =(0000000000000101) чаъ вч1 (О О О О О О О О О О О 1 0 0 О 1) ъач,ч,=(0000000100000001) чачач,в~ =(0000000000000001) Фиг. 6Л. Векторы, исиольауеиые в качестве бааиса дли кодов Рида — Миллера длины !6. два три четыре и т.
д- вплоть до пт одновременно, как показано на фиг. 5.1. Можно показать, что эти векторы линейно независимы. (Заметим, что на фиг. 5.1 строки можно переставить так„чтобы получилась матрица с единицами на главной диагонали и нулями всюду ниже главной диагонали.) Код Рида — Маллера порядка г определяется как код, базисом которого являются векторы уо, ъ ь..., и и все векторные произведения из г или меньшего числа этих векторов. Очевидно, скалярное произведение двух векторов равно О, если число единиц в векторном произведении четые, и равно 1, если оно нечетно.
Кроме того, для любого вектора ч его квадрат ив = у. Наконец, единственным произведением, содержащим нечетное число единиц, является произведение всех векторов уь ...„ и . Векторное произведение любого вектора из базиса кода порядка и на любой вектор из базиса кода порядка и — г — 1 является вектором из базиса для кода порядка сп — 1 и в нем содержится четное число единиц. Таким образом, любой вектор, принадлежащий коду порядка г, ортогонален любому базисному вектору кода порядка и — г — 1, т. е. любому вектору, являющемуся произведением пт — г — 1 или мень шего числа векторов уь ..., и, Так как сумма размерностей этих колов равна и, то, следовательно, каждый из них является двойственным по отношению к другому.
Отсюда следует также, что код Рида — Маллера порядка г является нулевым пространством матрицы, образованной векторами Ч43Ч4,...,У ивсемивекторными произведениями этих векторов в количестве не более чем лз — г — 1, взятыми в качестве ее строк. Поскольку матрица со строками УО, Уь ..., У,„является проверочной матрицей кода Хэммннга, исправляющего одну ошибку и обнаруживающего две ошибки, то этот код Хэмминга совпадает с кодом Рида — Маллера порядка гл — 2.
Важнейшая особенность кодов Рида — Маллера состоит в том, что декодирование для них может быть проведено простым способом. Легче всего это показать на примере. Рассмотрим код второго порядка для лт= 4. Это 116,11)-код, 11 информационных символов которого ао, аь аз. аг, аь азз, азз а4ь азь азь ам кодируются вектором аоуз + азч4 + азчз + а2У2 + а!у~ + 4243У4чз + а42узуз + + а41Ч4Ч~ + амУЗУ2+ а34УЗЧ! + а24ЧЗУ~ = (Ь! Ьг ° ° ° Ьл) ° Задача состоит в том, чтобы определить значения а по полученному вектору, несмотря на появившиеся ошибки. Заметим, что сумма первых четырех компонент как элементов поля из двух элементов равна О для всех базисных векторов, за исключением чзчз. Таким образом, если ошибок не было, то Ь4+Ь.+Ь.+Ьз=ам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
