Кодирование информации. Код Рида-Малера

Министерство образования и науки Украины

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

на тему "Кодирование информации. Код Рида-Малера "

по курсу "Кодирование и защита информации"

2003

Содержание

Введение

1 Избыточные коды

2 Алгоритм кодирования Рида-Малера

3 Тестовый пример

Вывод

Библиографический список

Приложение: Текст программы

Введение

Целью настоящей работы является закрепление знаний, получаемых в процессе изучения дисциплины, приобретение необходимых практических навыков применения методов кодирования информации. В данной курсовой работе рассматривается кодирование информации методом Рида-Малера. Код Рида-Малера относится к избыточным кодам. Заданием на данную работу было разработать алгоритм и программу кодирования и декодирования данных кодом Рида-Малера (16,11).

1. Избыточные коды

Избыточные коды – одно из наиболее эффективных средств обеспечения высокой достоверности передаваемых и принимаемых сообщений.

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

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

В кодах с одной проверкой на четность содержится всего один проверочный символ. Этот символ выбирается таким, чтобы его сумма по модулю два со всеми информационными символами равнялась нулю. Благодаря такому способу выбора проверочного символа кодовая комбинация содержит четное число единиц. И следовательно признаком искажения кодовой комбинации является нечетность единиц в принятой комбинации. Данный код позволяет только обнаруживать однократные ошибки и все ошибки нечетной кратности.

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

Корелляционный код. Удваиваются символы, при этом если в разряде информационной части стоит 0, то он заменяется на 01, а 1 – на 10. Сигналом ошибки является появление 00 или 11.

В инверсном коде используется повторение исходной комбинации следующим образом: если комбинация содержит нечетное число единиц, то вместо 1 ставится 0, а всесто 0 – 1. Если четное число единиц, то она удваивается без инверсии. На приемной стороне подсчитывается число единиц и, если оно четно, то вторая половинка инвертируется и складывается с первой. Если же число единиц четно, то вторая складывается с первой и должен получиться 0.

2 Алгоритм кодирования Рида-Малера

Коды Рида-Малера – это блоковые коды, которые строятся следующим образом:

 (1)  (2)  (3),

n-длина блока

K-число информационных символов

d-минимальное кодовое расстояние

m-положительное, условное число не меньше 3

s-порядок кода, который всегда меньше, чем m.

Т.е. в зависимости от порядка при одном и том же m можно получить разные коды.

m=4; s=1,2,3; n=2⁴=16.

Построение кодов Рида-Маллера сводится к следующему.

В начале строится производящая матрица G, первая строка которой содержит n единиц. Далее следует m строк, совокупность которых удобно рассматривать как (m*n) –матрицу, в качестве столбцов которой выбраны двоичные числа (начиная с нуля). Номера разрядов двоичных чисел удобно считать сверху вниз. Эти m строк определяют векторы первого порядка d. Далее идут строки векторов второго порядка, которые получаются из всех произведений двух строк первого порядка, затем - строки третьего порядка, являющиеся всеми произведениями трех строк первого порядка и т д.

Пример: т=3 s=2 п=2^т=2³=8

 

Для кодирования определяется общее число символов в блоке через информационные символы, суммируя ненулевые позиции соответствующего столбика, образующей матрицы. Единицы в столбцах матрицы G показывают, какие именно информационные символы Uk определяют значение символов Ui кодового слова.

Пусть пришла последовательность:

Получаем: 11101011

Декодирование осуществляется по мажоритарному принципу или принципу большинства.

Декодирование осуществляется вначале для всех информационных символов (кроме 1-го) на основе так называемых парных компонентов. Начинать запись таких уравнений надо с векторов максимального порядка.

В нашем примере s=2=> первым выписывается U_k5.

Для векторов 2-го порядка парными считаются компоненты:

00 ® 0

01 ® 1

На втором уровне сочетаний каждый 0 соединяется с каждой 1 попарно. Теперь в проверяемое равенство выписываются все объединенные позиции 1-го и 2-го уровней.

Вычисляем символ U_k6

Для U_k7:

При декодировании с помощью векторов 1-го порядка мы также точно пользуемся парными компонентами, но поскольку здесь 1-ый уровень, то мы объединяем просто 0 и 1, стоящую на соответствующих позициях, и, во-вторых, при декодировании в полученных уравнениях используют не исходное, а преобразованное уравнение, которое получается путем сложения по модулю два исходного уравнения и векторов 2-го порядка, (потому что матрица имеет 2-ой порядок),

После этого еще раз преобразуют исходное выражение: к полученному преобразованному выражению прибавляем векторы 1-го порядка, которые содержат единицу в соответствующем информационном разряде.

Если в полученном выражении получили все 1, то значит U_k1=1, а если все 0, то U_k1=0.

Если при передаче произошли искажения, то вычисляемый символ по каждой системе проверок выбирается по мажоритарному принципу, в том числе и для символа U_k1.