Коды Рида-Маллера

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:50, 14 мая 2016.

Определения

TemplateDifinitionIcon.svg Определение «Определение - РМ-код»

Код Рида-Маллера (РМ-код) состоит из множества векторов значений булевых функций от переменных, алгебраическая сумма которых не превосходит .

TemplateDifinitionIcon.svg Определение «Определение - Булева функция»
Булева функция - это произвольное отображение от переменных .
TemplateExampleIcon.svg Пример Пример 1: Булева функция

Таблинца истинности
000 0
001 1
010 1
011 0
100 1
101 0
110 1
111 0
TemplateDifinitionIcon.svg Определение «Определение - Вес функции»
Вес функции вес ее вектора значений.
TemplateExampleIcon.svg Пример Пример 2:

,

Так как 3 порождающих вектор, то из них можно составить 8 векторов.

Возьмем одночлены , затем произведения одночленов и т.д.:

;

;

.


Рис. 1.

Параметры кода

TemplateLemmaIcon.svg Лемма «Основные параметры кода:»
1) длина кода;
2) размерность;
3) Так как код линейный, то кодовое расстояние равно минимальному весу функции:


TemplateExampleIcon.svg Пример Пример 3:

,


TemplateExampleIcon.svg Пример Пример 4:

,

.


Теорема о кодовом расстоянии

TemplateTheoremIcon.svg Теорема Теорема
Доказательство

По индукции:

1. База индукции:

для справедливо;

2. В общем случае:

пусть при и любом , то , если . Пусть имеется:

Рис. 2.

1)

По предположению индукции для меньшего числа переменных это выполняется, следовательно:

2)

Если , то должно автоматически выполняться,следовательно:

3)

Последний случай, который необходимо рассмотреть:

, , следовательно:

Соответственно, справедлива оценка:

Таким образом все варианты рассмотрены. Теорема доказана.


Кодирование и Декодирование RM-кодов

Кодирование

Кодирование - вычисление вектора значений полинома Жегалкина с коэффициентами равными разрядам информационного вектора. Различие может состоять только в способе нумерования мономов (одночленов) полинома Жегалкина.

TemplateDifinitionIcon.svg Определение «1 Способ: упорядочивание мономов(одночленов)»
Сначала по степени, затем лексикографически.
TemplateDifinitionIcon.svg Определение «2 Способ: упорядочивание наборов степеней»
;
;
;
;
;
;
.

Декодирование

Как декодировать полученное слово?

  1. Перебором: в ближайшее кодовое слово;
  2. По синдрому (перебор столбцов проверочной матрицы);
  3. По таблице стандартного расположения;
  4. Мажоритарный алгоритм Рида (основан на свойствах полиномов Жегалкина)

Мажоритарный алгоритм Рида

000 0
001 1
010 1
011 0
100 1
101 0
110 1
111 0

Допустим, что АНФ имеет следующий вид:

.

Задача декодирования

Задачей декодирования является нахождение коэффициентов АНФ

Для вычисления может применяться метод сумм: .

Рассмотрим функцию и грань, соответствующую набору (**0):

,

.

Свойство 1:

Свойство 2: , следовательно а, значит,

Таким образом, получается т.е. можем проверить коэффициент двумя способами. Отсюда следует, что если ошибка одна, то мы ее обнаружим.

TemplateExampleIcon.svg Пример Пример 1:

Всего получаем 8 равных подсчетов для , согласно методу сумм, т.е., если:

ассоциированных с данным набором граней.

Примечание: Ошибки, накопленные при одной оценке, никак не влияют на другие оценки.

Грани разбивают все пространство на кусков и полностью заполняют пространство.

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

Каждый набор звездочек определяет свой коэффициент:

:


TemplateExampleIcon.svg Пример Пример 2:

- код и сообщение ;

следовательно и других нет.

Дальше мы рассматриваем функцию ,

Должны получить новую функцию и :

На выходе появится вектор:


Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.