Коды проверяющие ошибки

Содержание.

Код Хемминга………………………………………………………..2

История………………………………………………………………………….2

Самоконтролирующиеся коды……………………………………………2

Самокорректирующиеся коды…………………………………………….3

 

Код Грея…………………………………………………………….14

Код Грея, рефлексный двоичный код…...........................................14

Преобразование двоичного кода в код Грея……………………......14

Преобразование кода Грея в двоичный код…………………………15

Генерация кодов Грея……………………………………………………...16 

Турбо код……………………………………………………………17

История………………………………………………………………………...17

Кодирование………………………………………………………………….18

Кодовая скорость……………………………………………………….......19

Декодирование……………………………………………………………….20

Одна итерация итеративного турбо-декодера при двухкаскадном кодировании…………………………………………………………………..21

Трёхитерационный турбо декодер при двухкаскадном кодировании............................................................................................21

Преимущества и недостатки турбо-кодов……………………………..21

Примение турбо - кодов……………………………………………………22

 

Код Хемминга.

История

В середине 40-х годов Ричард Хемминг работал в знаменитых Лабораториях Белла на счётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки,скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машине с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.

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

Самоконтролирующиеся коды

Коды Хемминга являются самоконтролирующимися кодами, т.е  кодами, позволяющими автоматически  обнаруживать наиболее вероятные ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.

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

Самокорректирующиеся коды

Коды, в которых  возможно автоматическое исправление  ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенству  или  , где m -количество основных двоичных разрядов кодового слова. Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице № 1

Диапазон m	kmin
1	2
2-4	3
5-11	4
12-26	5
27-57	6

Имея m+k разрядов, самокорректирующийся код можно построить следующим образом.

Присвоим каждому  из разрядов свой номер - от 1 до m+k; запишем  эти номера в двоичной системе  счисления. Поскольку 2^k > m + k ,каждый номер можно представить, очевидно, k-разрядным двоичным числом.

Предположим далее, что все m+k разрядов кода разбиты на контрольные группы, которые частично перекрываются, причем так, что единицы в двоичном представлении номера разряда указывают на его принадлежность к определённым контрольным группам. Например: разряд № 5 принадлежит к 1-й и 3-й контрольным группам, потому что в двоичном представлении его номера 5₁₀ = …000101₂ - 1-й и 3-й разряды содержат единицы.

Среди m+k разрядов кода при этом имеется k разрядов, каждый из которых принадлежит

только к одной  контрольной группе:

Разряд № 1: 1₁₀ = …000001₂ принадлежит только к 1-й контрольной группе.

Разряд № 2: 2₁₀ = …000010₂ принадлежит только к 2-й контрольной группе.

Разряд № 4: 4₁₀ = …000100₂ принадлежит только к 3-й контрольной группе.

Разряд № 2^k − 1 принадлежит только к k-й контрольной группе.

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

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

Например, довольно распространен  код Хеминга с m=7 и k=4.

Пусть исходное слово (кодовое слово без контрольных разрядов) - 0110101₂.

Обозначим P_i - контрольный разряд №i; а D_i - информационный разряд №i, где i = 1,2,3,4…

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
Информационное кодовое  слово :			0		1	1	0		1	0	1
p1	1		0		1		0		1		1
p2		0	0			1	0			0	1
p3				0	1	1	0
p4								0	1	0	1
Кодовое слово с контрольными разрядами:	1	0	0	0	1	1	0	0	1	0	1

Интересно посмотреть, как перекрываются контрольные группы в данном случае (Рис №1). Первая группа контролирует разряды № 3,7,5 исходного кода, вторая — 3,7,6… (№ группы = № контрольного разряда). Очевидно, что они частично перекрываются.

Рис.№1 Первая группа контролирует разряды № 3,7,5 исходного кода, вторая — 3,7,6… Очевидно что они частично перекрываются

Предположим теперь, для примера, что при передаче данного кодового слова 10001100101 произошла ошибка в 11–м разряде, так, что было принято новое кодовое слово 10001100100. Произведя в принятом коде проверку четности внутри контрольных групп, мы обнаружили бы, что количество единиц нечетно в 1-й,2-й и 4-й контрольных группах, и четно в 3-й контрольной группе. Это указывает, во-первых, на наличие ошибки, во-вторых, означает, что номер ошибочно принятого разряда в двоичном представлении содержит единицы на первом, втором и четвёртом местах и нуль - на третьем месте, т.к ошибка только одна, и 3-я контрольная сумма оказалась верной.

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7	Контроль  по четности в группе	Контрольный бит
Переданное  кодовое слово:	1	0	0	0	1	1	0	0	1	0	1
Принятое  кодовое слово:	1	0	0	0	1	1	0	0	1	0	0
p1	1		0		1		0		1		0	Fail	1
p2		0	0			1	0			0	0	Fail	1
p3				0	1	1	0					Pass	0
p4								0	1	0	0	Fail	1

	p4	p3	p2	p1
В двоичном представлении	1	0	1	1
В десятичном представлении	8		2	1	Σ = 11

Из таблицы следует, что ошибка произошла в 11-м разряде  и её можно исправить. Построенный  код, разумеется, не рассчитан на возможность  одновременной ошибки в двух разрядах.

Например (Рис №2), когда ошибки одновременно прошли в 3-м и 7-м разрядах исходного кода, первый и второй контрольные биты даже не замечают подмены.

Рис.№2 Когда  ошибки прошли в 3-м и 7-м разрядах исходного кода, первый и второй контрольные биты даже не замечают ошибки

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

Например, предположим  теперь, что при передаче данного  кодового слова 10001100101 произошли ошибки в 3-м и 6-м разрядах, так, что принято  кодовое слово 10101000101.

№ разряда:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011
Распределение контрольных и информационных разрядов	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7	Контроль  по четности в группе	Контрольный бит
Переданное  кодовое слово:	1	0	0	0	1	1	0	0	1	0	1
Принятое  кодовое слово:	1	0	1	0	1	0	0	0	1	0	1
p1	1		1		1		0		1		1	Fail	1
p2		0	1			0	0			0	1	Pass	0
p3				0	1	0	0					Fail	1
p4								0	1	0	1	Pass	0