Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

18. Многоступенчатое голосование и коды Рида - Маллера

Мы расскажем здесь о кодах, для которых найден замечательный алгоритм исправления ошибок, сыгравший важнейшую роль в развитии методов мажоритарного декодирования.

Проще всего начать с расширенного (8,4)-кода Хемминга. Нетрудно убедиться, что этот код дуален самому себе, т. е. что его проверочная матрица служит для него и порождающей:


Этот код не является полностью ортогонализуемым (см. § 17, задача 2). Значит ли это, что голосование для этого кода невозможно? Оказывается, нет.

Идея, которую мы проиллюстрируем на данном примере, состоит в следующем. Если нельзя составить нужной системы ортогональных проверок для каждого символа в отдельности, то, может быть, это удастся сделать для определенных линейных комбинаций этих символов.

Пусть υ = (α0, α1, α2, α3, α4, α5, α6, α7) - произвольное кодовое слово. Оно, как обычно, может быть записано в виде:

υ = a0g0 + a1g1 + a2g2 + a3g3.

Выясним, как связаны координаты αi вектора υ с коэффициентами равенства (1). Заметим, что сумма первых двух координат каждого из векторов g0, g1 и g2 равна 0, тогда как для вектора g3 она равна 1. Поэтому сумма соответствующих координат вектора υ равна а3, т. е.

а3 = α0 + α1. (2)

Совершенно так же убеждаемся, что верны равенства:

а3 = α2 + α3,
а3 = α4 + α5, (3)
а3 = α6 + α7.

Нетрудно понять, что соотношения (2) и (3) представляют систему ортогональных проверок для коэффициента а3. Для коэффициентов а2 и а1 дело обстоит аналогично и ортогональные проверки для них таковы:

а2 = α0 + α2,
а2 = α1 + α3,
а2 = α4 + α6,
а2 = α5 + α7,
а1 = α0 + α4,
а1 = α1 + α5,
а1 = α2 + α6,
а1 = α3 + α7. (4)

Применяя к полученным проверкам принцип большинства, мы найдем верные значения коэффициентов a1, а2, а3, если произошло не более одной ошибки. В случае двойной ошибки при определении хотя бы одного из коэффициентов голоса распределятся поровну и ошибка будет только обнаружена.

Предположим, что верные значения коэффициентов а1, a2, а3 найдены. Тогда еще один этап голосования позволяет определить также и верное значение коэффициента а0. Сделать это совсем несложно. В самом деле, рассмотрим разность

υ1 = υ - a1g1 - a2g2 - a3g3.

В случае безошибочной передачи, в силу равенства (1), υ1 = a0g0, т. е. все координаты вектора υ1 равны а0. Значит, либо все они равны нулю, либо все равны единице. Поэтому в качестве верного значения а0 выбираем то, которое преобладает среди координат вектора υ1.

Определив значения коэффициентов а0, a1, a2, а3, мы без труда восстанавливаем кодовое слово согласно равенству (1).

Пример. Пусть принято слово 01110110, содержащее одиночную ошибку. Для декодирования обращаемся к равенствам (2), (3) и (4), которые в данном случае дают следующие результаты:

а1 = 0, а2 = 1, a3 = 1,
а1 = 0, а2 = 0, a3 = 0,
а1 = 0, а2 = 1, a3 = 1,
а1 = 1, а2 = 1, a3 = 1.

По большинству значений находим: а1 = 0; а2 = а3 = 1. Тогда

υ1 = (01110110) - (00110011) - (01010101) = (00010000),

откуда а0 = 0. Следовательно,

υ = g2 + g3 = (01100110).

Этот изящный метод декодирования может быть применен к так называемым кодам Рида - Маллера (сокращенно - РМ-коды), которые мы и хотим сейчас рассмотреть.

РМ-код первого порядка определяется как код, дуальный к расширенному коду Хемминга, т. е. как код, порождающая матрица которого совпадает с проверочной матрицей расширенного кода Хемминга. Таким образом, расширенному (n, k)-коду Хемминга (n = 2m, k = 2m - m - 1) отвечает (n, n-k)-код Рида - Маллера. При m = 3 оба кода совпадают: расширенный (8,4)-код Хемминга дуален самому себе. При m = 4 получаем (16,5)-код Рида - Маллера первого порядка с порождающей матрицей


Алгоритм декодирования для этого кода практически не отличается от рассмотренного выше алгоритма для (8,4)-кода. Действительно, если

υ = a0g0 + a1g1 + a2g2 + a3g3 + a4g4,

то, например,

а4 = α0 + α1 = α2 + α3 = α4 + α5 = α6 + α7 = α8 + α9 = α10 + α11 = α12 + α13 = α14 + α15.

Таким образом, для коэффициента а4 имеем 8 ортогональных проверочных соотношений. Такое же число ортогональных проверок получается и для каждого из коэффициентов а1, а2, а3.

Следовательно, если произошло не более трех ошибок, то в первом "туре" голосования удается восстановить верные значения коэффициентов а1, а2, а3, а4. Во втором "туре", действуя совершенно так же, как и в случае (8,4)-кода, получаем верное значение для а0. После этого по найденным значениям коэффициентов целиком восстанавливаем кодовое слово. Итак, (16,5)-код Рида - Маллера исправляет любые ошибки, если они имеются не более чем в трех символах, и обнаруживает ошибки в четырех символах. Можно убедиться, что двух этапов голосования достаточно для любого РМ-кода первого порядка.

При построении кодов Рида - Маллера более высоких порядков используется покомпонентное умножение векторов, определяемое следующим образом: если υ = (α1, α2, ..., αn), u = (β1, β2, ..., βn), то

υ ○ u = (α1β1, α2β2, ..., αnβn).

Покажем теперь, как по произвольному РМ-коду первого порядка строятся РМ-коды r-го порядка (r > 1). Пусть строками порождающей матрицы РМ-кода первого порядка являются векторы g0, g1, ...,gm. Составим из этих векторов всевозможные произведения, содержащие не более r сомножителей. Добавим эти произведения в качестве дополнительных строк к строкам g0, g1, ...,gm. Полученную в результате матрицу и будем считать порождающей матрицей РМ-кода r-го порядка. Например, для РМ-кода второго порядка, соответствующего (16,5)-коду Рида - Маллера первого порядка, эта матрица имеет вид


Этот код исправляет любые одиночные и обнаруживает двойные ошибки, а мажоритарное декодирование для него может быть осуществлено в три этапа. Если υ кодовое слово, то

υ = a0g0 + a1g1 + ... + a4g4 + a12g1○g2 + a13g1○g3 + ... + a34g3○g4. (5)

На первом этапе определяем верные значения коэффициентов аij, для каждого из которых имеем четыре ортогональных проверочных соотношения. Например, для коэффициента а34 они таковы:

а34 = α0 + α1 + α2 + α3,
а34 = α4 + α5 + α6 + α7,
а34 = α8 + α9 + α10 + α11,
а34 = α12 + α13 + α14 + α15.

После определения коэффициентов aij составляем разность

υ1 = υ - a12g1○g2 - ... - a34g3○g4 = (α'0, α'1, ..., α'15).

Поскольку при безошибочной передаче

υ1 = a0g0 + a1g1 + a2g2 + a3g3 + a4g4,

то проверочные соотношения для определения а1, а2, а3, а4 (это второй этап голосования) таковы же, как для РМ-кода первого порядка. К примеру,

а4 = α'0 + α'1 = α'2 + α'3 = α'4 + α'5 = α'6 + α'7 = α'8 + α'9 = α'10 + α'11 = α'12 + α'13 = α'14 + α'15.

Наконец, на третьем этапе составляем разность

υ1 - a1g1 - a2g2 - a3g3 - a4g4 = (α″0, α″1, ..., α″15)

и по большинству значений координат α″i определяем значение а0. После завершения третьего этапа кодовое слово восстанавливается по формуле (5).

Подобная процедура декодирования распространяется на РМ-коды произвольных порядков; при этом для кода r-го порядка число этапов голосования равно r+1 и для кода длины 2m число ортогональных проверок на первом этапе равно 2m-r (на каждом последующем этапе число проверок удваивается). Таким образом, может быть исправлено 2m-r-1 - 1 ошибок, а 2m-r-1 ошибок всегда обнаруживается.

В настоящее время открыто достаточно много кодов, для которых применимы подобные алгоритмы декодирования. Их описание и способы построения ортогональных проверок базируются на различных комбинаторных и геометрических конструкциях.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru