21. Кодирование сообщений по проверочной матрице.

Проверочная матрица состоит из m строк и n столбцов. Образуется из порождающей матрицы следующим образом:

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

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

Т.е., следовательно, проверочная матрица

С пом. этой матрицы операция кодирования осущ. след. образом:

Позиции, занимаемые единицами в i-й строке подматрицы определяют те инф. разряды, кот. должны участвовать в формир. i-го проверочного разряда. ПРИМЕР:

a1 a2 a3 a4 b1 b2 b3 a1 a2 a3 a4 b1 b2 b3

22. Обнаружение ошибки в принятой комбинации по проверочной матрице.

Проверочная матрица Н состоит из m строк и n столбцов.

Алгоритм нахождения ошибок предельно просто реализуется, поэтому получил распространение.

Кодирование: находим в столбце контрольного символа единицу, суммируем все информационные символы, которые в этойй строке также равны единице

a1 a2 a3 a4 b1 b2 b3

Т.е b1=a1+a2+a3; b2=a1+a2+a4; b3=a1+a3+a4;

Декодирование(и обнаружение ошибок) декодер по хранящейся в нем проверочной матрице осуществляет процесс суммирования контрольных и информационных символов (по единицам)

K1=a1+a2+a3+b1

K2=a1+a2+a4+b2

K3=a1+a3+a4+b3

Если все символы К равны нулю – ошибок нет, иначе –перепосылка.

23. Построение порождающей матрицы кода Хемминга d=3.

Подобранные опред. образом «k» исх. код. комбинаций однозначно определяют систематический код. Эти комбинации запис. в виде матрицы G_n,k, состоящей из “k” строк и “n” столбцов – производящей (образующей) матрицы.:

(1)

Производящая матрица может быть представлена двумя подматрицами – информационной и проверочной

В качестве информационной подматрицы удобно брать единичную квадратную матрицу в канонической форме

(2)

24. Исправление ошибок систематическим кодом с помощью кодов-спутников.

1) Исправление ошибок с использованием кодов-спутников;

2) На основании проверочной матрицы;

3) На основании проверочных чисел.

Сущность способа:

-рабочим комбинациям ставится в соответствие доп. комбинации – спутники с заданным числом ошибок

- при приеме декодер сравнивает принятую комбинацию и относит ее к какому либо виду.

Идея метода заключается в следующем:, где Е – многочлен ошибки, F – вх. комбинация

d=3, s=1(исправляет одиночную ошибку)

F=(1)110011. Она находится в первой графе матрицы, следовательно – ошибочный первый бит.

Недостаток:

-большие объемы памяти

-большое время обработки (сравнение с декодирован.)

ВЫВОД – на практике данный метод не эффективен

25. Исправление ошибок систематическим кодом Хемминга d=3 по синдрому.

Суть метода исправления с помощью пров. матрицы (по синдрому): при кодировании комбинации по определ. проверкам определяются значения контрольных символов и затем передаются в КС. На приёмной стороне по принимаемым информ. символам, в соответствии с заданными проверками определяются проверочные символы.

. Принятые контрольные символы суммируются по модулю 2 с вновь прибывшими:

-

Синдром указывает наличие и местоположение

ошибки в принятой комбинации.

→ Синдром Особенности синдрома:

1) не привязан к какой-либо комбинации;

2) синдром соответствует нескольким комбинациям ;k – кол-во информационных символов.

3) комбинаций с трансформацией ошибок. На практике синдром изкомбинаций соответствует наиболее вероятной комбинации.

Пример: Возьмем проверочную матрицу:

Если код использовался для исправления ошибок, то при декодировании необходимо ставить в соответствие синдром и вид исправимой ошибки.

Комбинация ошибок:

a1 a2 a3 a4 b1b2 b3

е1= 1 0 0 0 0 0 0

для этой комбинации ошибок применим правило проверок:

26. Исправление ошибок систематическим кодом Хемминга d=3 по проверочному числу.

d=3 (r=1;s=1)

n=k+m

На приёмной стороне данные группы провер. на чётность. Количество этих проверок будет равно количеству контрольных символов.

Проверки на четность m-я, (m-1) ……. 2-я, 1-я

Результат проверки 1 , 0 ……. 1 , 0

В результате осуществляется m проверок в регистре образ. 2-ичное число- проверочное число (ПЧ), которое указывает номер позиции кода, на которой находится ошибка.

Требования к проверочному числу:

ПЧ д. указывать ошибок на информационных позициях кода, ошибок на контрольных позициях кода и ошибок

Таблица проверок:

Nпров	Пров.поз.	последовательность проверок
1	1	1,3,5,7,9,11,13,15…
2	2	2,3,6,7,10,11,14,15…
3	4	4,5,6,7,12,13,14,15…
4	8	8,9,10,11,12,13,14,15

1,2,4,8 – встречаются по одному разу в проверочных группах.

–определяется местоположение контрольных символов.

27. Код Хемминга d=3 с перетасованными контрольными разрядами.ислу.

Исправление ошибок кода в коде Хэмминга по проверочному числу (d=3, r=1, s=1) На приемной стороне группы символов проверяются на четность и результат проверки записывается в регистр. Количество проверок = числу контрольных символов n=k+m, будет m проверок.

Проверки на четность m m-1 m-2 … 3 2 1

Результат проверки 0 1 ….. 0 1 0

В результате осуществляется m проверок в регистре образ. 2-ичное число- проверочное число (ПЧ), которое указывает номер позиции, на которой находится ошибка.

Количество комбинаций пров. числа: – код на все сочетания,.

Требования к проверочному числу:

ПЧ д. указывать ошибок на информационных позициях кода, ошибок на контрольных позициях кода и ошибок

Таблица Хемминга

n	1	2	3	4	5	6	7	8
m	1	2	2	3	3	3	3	4
k	0	0	1	1	2	3	4	4

Существует таблица проверок.

Nпров	Пров.поз.	последовательность проверок
1	1	1,3,5,7,9,11,13,15…
2	2	2,3,6,7,10,11,14,15…
3	4	4,5,6,7,12,13,14,15…
4	8	8,9,10,11,12,13,14,15

Место положения контрольных символов: