Коды, исправляющие дефекты

Министерство образования  и науки РФ

Федеральное государственное  бюджетное образовательное учреждение

Высшего профессионального  образования

Математический факультет

Специальность «Компьютерная  безопасность»

 

 

 

 

Курсовая работа на тему:

«Коды, исправляющие дефекты»

 

 

 

 

 

 

Автор:

Мойсеенко С. С.

Научный руководитель:

Семыкина Н. А.

 

 

 

Тверь 2013

Оглавление

Принципы помехоустойчивого кодирования 3

Декодирование помехоустойчивых кодов 4

Способ сравнения. 4

Синдромный способ 4

Мажоритарное декодирование 4

Классификация корректирующих кодов 5

Код с постоянным весом 5

Код с четным числом единиц 6

Код Хэмминга 6

Матричное представление систематических  кодов 10

Декодирование циклических кодов 11

Список использованной литературы: 12

 

 

 

Принципы помехоустойчивого кодирования

Помехоустойчивым (корректирующим) кодированием называется кодирование при котором осуществляется обнаружение либо обнаружение и исправление ошибок в принятых кодовых комбинациях.

Возможность помехоустойчивого кодирования  осуществляется на основании теоремы, сформулированной Шенноном, согласно ей:

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

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

Рисунок 1 - Случаи приема закодированного сообщения

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

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

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

Помехоустойчивое кодирование  может осуществляться двумя способами: с обнаружением ошибок либо с исправлением ошибок. Возможность кода обнаруживать или исправлять ошибки определяется кодовым расстоянием.

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

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

Декодирование помехоустойчивых кодов

Декодирование - это процесс перехода от вторичного отображения сообщения к первичному алфавиту.

Декодирование помехоустойчивых кодов  может осуществляться тремя способами: способом сравнения, синдромным и мажоритарным.

Способ  сравнения.

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

Синдромный  способ 

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

Мажоритарное  декодирование 

Этот способ основано на том, что каждый информационный символ кодовой комбинации определяется нескольким линейными выражениями через другие символы кодовой комбинации. Если принята комбинация без ошибок, то все соотношения остаются и все выражения дают одинаковые результаты (единицу или ноль). При ошибке в одном из разрядов эти соотношения нарушаются, в результате чего одни линейные выражения равны нулю, а другие единице. Решение о принятом символе определяется по большинству: если в результате вычислений выражений больше нулей, то принимается решение о принятии нуля, если больше единиц, то принимается решение о приеме единицы. Если, при декодировании, результаты вычисления выражений дают одинаковое число единиц и нулей, то при определении принятого символа приоритет имеет принятый символ, значение которого в данный момент определяется.

Классификация корректирующих кодов

Классификация корректирующих кодов  представлена схемой (рисунок 2)

Блочные — это коды, в которых передаваемое сообщение разбивается на блоки и каждому блоку соответствует своя кодовая комбинация (например, в телеграфии каждой букве соответствует своя кодовая комбинация).

Рисунок 2 - Классификация корректирующих кодов

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

Неразделимые — это коды, в кодовых комбинациях которых нельзя выделить проверочные разряды.

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

Систематические (линейные) — это коды, в которых проверочные символы определяются как линейные комбинации информационных символов, в таких кодах суммирование по модулю два двух разрешенных кодовых комбинаций также дает разрешенную комбинацию. В несистематических кодах эти условия не выполняются.

Код с постоянным весом

Данный код относится к классу блочных не разделимых кодов. В нем  все разрешенные кодовые комбинации имеют одинаковый вес. Примером кода с постоянным весом является Международный  телеграфный код МТК-3. В этом коде все разрешенные кодовые комбинации имеют вес равный трем, разрядность  же комбинаций n=7. Таким образом, из 128 комбинаций (N₀ = 2⁷ = 128) разрешенными являются Nа = 35 (именно столько комбинаций из всех имеют W=3). При декодировании кодовых комбинаций осуществляется вычисление веса кодовой комбинации и если W≠3, то выносится решение об ошибке. Например, из принятых комбинаций 0110010, 1010010, 1000111 ошибочной является третья, т. к. W=4. Данный код способен обнаруживать все ошибки нечетной кратности и часть ошибок четной кратности. Не обнаруживаются только ошибки смещения, при которых вес комбинации не изменяется, например, передавалась комбинация 1001001, а принята 1010001 (вес комбинации не изменился W=3). Код МТК-3 способен только обнаруживать ошибки и не способен их исправлять. При обнаружении ошибки кодовая комбинация не используется для дальнейшей обработки, а на передающую сторону отправляется запрос о повторной передаче данной комбинации. Поэтому данный код используется в системах передачи информации с обратной связью.

Код с четным числом единиц

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

При декодировании осуществляется поразрядное суммирование по модулю два всех элементов принятой кодовой  комбинации и если результат равен  единице, то принята комбинация с  ошибкой, если результат равен нулю, то принята разрешенная комбинация. Например:

101101 = 1 + 0 + 1 + 1 + 0 + 1 = 0 — разрешенная  комбинация

101111 = 1 + 0 + 1 + 1 + 1 + 1 = 1 — запрещенная  комбинация.

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

Код Хэмминга

Код Хэмминга относится к классу блочных, разделимых, систематических  кодов. Кодовое расстояние данного  кода d₀=3 или d₀=4.

Блочные систематические коды характеризуются  разрядностью кодовой комбинации n и количеством информационных разрядов в этой комбинации k остальные разряды  являются проверочными (r):

r = n - k.

Данные коды обозначаются как (n,k).

Рассмотрим код Хэмминга (7,4). В  данном коде каждая комбинация имеет 7 разрядов, из которых 4 являются информационными,

При кодировании формируется кодовая  комбинация вида:

а₁ а₂ а₃ а₄ b₁ b₂ b₃

где а_i — информационные символы;

b_i — проверочные символы.

В данном коде проверочные элементы b_i находятся через линейные комбинации информационных символов a_i, причем, для каждого проверочного символа определяется свое правило. Для определения правил запишем таблицу синдромов кода (таблица 1), в которой записываются все возможные синдромы, причем, синдромы имеющие в своем составе одну единицу соответствуют ошибкам в проверочных символах:

• синдром 100 соответствует ошибке в проверочном символе b₁;
• синдром 010 соответствует ошибке в проверочном символе b₂;
• синдром 001 соответствует ошибке в проверочном символе b₃.

Синдромы с числом единиц больше 2 соответствуют ошибкам в информационных символах. Синдромы для различных  элементов кодовой комбинации а_i и b_i должны быть различными.

Таблица 1 — Синдромы кода Хэмминга (7;4)

Число синдрома		Элементы синдрома			Элементы кодовой комбинации
		С1	С2	С3
1		0	0	1	b3
2		0	1	0	b2
3		0	1	1	a1
4		1	0	0	b1
5		1	0	1	a2
6		1	1	0	a3
7		1	1	1	a4

Определим правило формирования элемента b₃. Как следует из таблицы, ошибке в данном символе соответствует единица в младшем разряде синдрома С4. Поэтому, из таблицы, необходимо отобрать те элементы а_i у которых, при возникновении ошибки, появляется единица в младшем разряде. Наличие единиц в младшем разряде, кроме b₃,соответствует элементам a₁, a₂ и a₄. Просуммировав эти информационные элементы получим правило формирования проверочного символа:

b₃ = a₁ +    a₂  +  a₄

Аналогично определяем правила  для b₂ и b₁:

b₂ = a₁ +  a₃ + a₄

b₁ = a₂ +  a₃ + a₄

Пример 1: необходимо сформировать кодовую комбинацию кода Хэмминга (7,4) соответствующую информационным символам 1101.

В соответствии с проверочной матрицей определяем b_i:

b₁ = 1 +  0 + 1 = 0; b₂ = 1 + 0 + 1=1; b₃ = 1 + 1 + 1 = 1.

Добавляем проверочные символы  к информационным и получаем кодовую комбинацию:

Biр = 1101001.

В теории циклических кодов все  преобразования кодовых комбинаций производятся в виде математических операций над полиномами (степенными функциями). Поэтому двоичные комбинации преобразуют в полиномы согласно выражения:

Аi(х) = а_n-1x^n-1 + а_n-2x^n-2 +…+ а₀x⁰

где a_n-1, … коэффициенты полинома принимающие значения 0 или 1. Например, комбинации 1001011 соответствует полином

Аi(х) = 1*x⁶ + 0*x⁵ + 0*x⁴ + 1*x³ + 0*x² + 1*x+1*x⁰ = x⁶ + x³ + x+1.

При формировании кодовых комбинаций над полиномами производят операции сложения, вычитания, умножения и  деления. Операции умножения и деления  производят по арифметическим правилам, сложение заменяется суммированием  по модулю два, а вычитание заменяется суммированием.

Разрешенные кодовые комбинации циклических  кодов обладают тем свойством, что  все они делятся без остатка  на образующий или порождающий полином G(х). Порождающий полином вычисляется с применением ЭВМ. В приложении приведена таблица синдромов.

Этапы формирования разрешенной  кодовой комбинации разделимого  циклического кода Biр(х).

1.  Информационная кодовая комбинация Ai преобразуется из двоичной формы в полиномиальную (Ai(x)).

2.  Полином Ai(x) умножается на х^r,

Ai(x)*x^r

где r количество проверочных разрядов:

r = n — k.

3.  Вычисляется остаток от деления R(x) полученного произведения на порождающий полином:

R(x) = Ai(x)*x^r/G(x).

4.  Остаток от деления (проверочные разряды) прибавляется к информационным разрядам:

Biр(x) = Ai(x)*x^r + R(x).

5.  Кодовая комбинация Bip(x) преобразуется из полиномиальной формы в двоичную (Bip).

Пример 2. Необходимо сформировать кодовую комбинацию циклического кода (7,4) с порождающим полиномом G(x)=х³+х+1, соответствующую информационной комбинации 0110.