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

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

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

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

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

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

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=24=16.

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

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

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

/> />

/>/>

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

/>

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

/>

Получаем: 11101011

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

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

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

/>


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

00 ® 0

01 ® 1

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

/>

/>

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

/>


/>

Для Uk7:

/>

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

/>/>

/>/>

/>

/>


/>

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

/>

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

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

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

В качестве тестового примераиспользовалась комбинация 11001010000.

В задании к курсовому проектууказано, что n=16, а k=11.Таким образом получили образующую матрицу, которая имеет следующий вид:

/>


Построение матрицы реализованопрограммно для заданных n и k.

После кодирования исходной комбинации11001010000 по полученной образующей матрице получиликомбинацию1010111101010000. При этом мы суммируем те разряды исходнойкомбинации, на соответствующих позициях которых, в рассматриваемом столбцеобразующей матрицы, стоят единицы. Например, возьмем четвертый столбец. Единицыимеются в разрядах 1,2,3,6. При суммировании этих разрядов получим 0. То есть взакодированной комбинации в четвертом разряде получили 0:

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


Вывод

В ходе курсовой работы был исследованпростой помехоустойчивый код, а именно код Рида-Малера. Данный код обнаруживаетошибки, но не исправляет их. Рассматривался случай, когда n=16,k=11, поэтому в матрице присутствуют только векторапервого и второго порядка. Однако если появится необходимость использоватьтакже вектора третьего порядка, то образующая матрица станет значительнобольше, что не выгодно с точки зрения экономии памяти. При этом такжеувеличится длина закодированной комбинации, что увеличит время передачисообщения по каналу связи.


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

1.        Березюк Н.Т. «Кодирование Информации» — 1978.

2.        Конспект лекций по дисциплине «Кодирование и защита информации».


Приложение

Текстпрограммы

еще рефераты
Еще работы по информатике, программированию