Двухмерный контроль паритета

Двухмерный контроль паритета позволяет:

1. Обнаруживать и исправлять одиночные ошибки.

2. Обнаруживать двойные ошибки.

Способность приемника обнаруживать и исправлять ошибки называют прямым исправлением ошибок (Forward Error Correction, FEC). Двухмерный контроль паритета применяются в устройствах хранения данных. Такие методы При двухмерном контроле вычисляются множественные биты паритета четности.

Кодирование данных и передача по линии связи :

1. Данное, состоящее из (n∙m)-разрядов разбивается на n-фрагментов, состоящих из m-разрядов.

Например, данное, состоящее из 16-разрядов, разбивается на 4 фрагмента длиной по 4 разряда (n = 4 фрагмента, m = 4 разряда).

Фрагмент 3

Фрагмент 2

Фрагмент 1

Фрагмент 0

2. Фрагменты образуют прямоугольную матрицу, содержащую 4 строки и 4 столбца.

	J3	J 2	J 1	J 0
I3
I2
I1
I0

где , , , – номера строк; , , , – номера столбцов.

Соответствие прямоугольной матрицы и исходного сообщения приведено в таблице.

Фрагмент 3 (строка I3)

Фрагмент 2 (строка I2)

Фрагмент 1 (строка I1)

Фрагмент 0 (строка I0)

3. Для каждой строки и столбца вычисляются биты паритета четности.

	J3	J 2	J 1	J 0	PI
I3					РI3
I2					РI2
I1					РI1
I0					РI0
PJ	РJ3	РJ2	РJ1	РJ0

где Р_I3, Р_I2, Р_I2 , Р_I0 - паритеты строк; Р_J3, Р_J2, Р_J1, Р_J0 - паритеты столбцов.

4. Для всех битов паритета строк и столбцов вычисляется дополнительный бит паритета паритетов Р_IJ строк и столбцов паритета .

	J3	J 2	J 1	J 0	PI
I3					РI3
I2					РI2
I1					РI1
I0					РI0
PJ	РJ3	РJ2	РJ1	РJ0	РIJ

5. Из фрагментов и битов паритета, содержащих (n+1)∙(m+1)-разрядов, образуется сообщение:

Р_I3 Р_I2 Р_I2 Р_I0 Р_J3Р_J2Р_J1Р_J0Р_IJ.

6. Передающий узел посылает по линии связи сообщение:

Р_I3 Р_I2 Р_I2 Р_I0 Р_J3Р_J2Р_J1Р_J0Р_IJ.

.

Прием и проверка данных:

1. Приемный узел принимает сообщение:

Р_I3 Р_I2 Р_I2 Р_I0 Р_J3Р_J2Р_J1Р_J0Р_IJ.

2. Сообщение разбивается на (n + 1) - фрагментов, состоящих из (m + 1) - разрядов:

		J3	J 2	J 1	J 0	PI
	I3					РI3
	I2					РI2
	I1					РI1
	I0					РI0
	PJ	РJ3	РJ2	РJ1	РJ0	РIJ

3. Для каждой строки вычисляются синдромы S_I3, S_I2, S_I1, S_I0, S_Р. Для каждого столбца вычисляются синдромы S_J3, S_J2, S_J1, S_J0, S_Р

	J3	J 2	J 1	J 0	PI	SI
I3					РI3	SI3
I2					РI2	SI2
I1					РI1	SI1
I0					РI0	SI0
PJ	РJ3	РJ2	РJ1	РJ0	РIJ	SРIJ
SJ	SJ3	SJ2	SJ1	SJ0	SРJI

3. Проверка на наличие ошибок:

- если все синдромы равны нулю, то ошибки нет;

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

Например, если синдромы S_I2 = 1 и Р_J0 =1, то на пересечении строки I₂ и столбца J₀ находится испорченный бит D₈, который может быть исправлен.

	J3	J 2	J 1	J 0	PI	SI
I3					РI3	SI3
I2					РI2	SI2
I1					РI1	SI1
I0					РI0	SI0
PJ	РJ3	РJ2	РJ1	РJ0	РIJ	SРIJ
SJ	SJ3	SJ2	SJ1	SJ0	SРJI

- если обнаруживается более двух синдромов равных единице, то выявляется наличие множественных ошибок.

Например, если синдромы строк S_I2 = 1, S_I0= 1 и столбцов S_J3 = 1, Р_J0 =1, то на пересечении строк I₂, I₀ и столбцов J₃, J₀ находятся биты , D₈, , ,которые не могут быть идентифицированы, а поэтому и исправлены.

	J3	J 2	J 1	J 0	PI	SI
I3					РI3	SI3
I2					РI2	SI2
I1					РI1	SI1
I0					РI0	SI0
PJ	РJ3	РJ2	РJ1	РJ0	РIJ	SРIJ
SJ	SJ3	SJ2	SJ1	SJ0	SРJI

Сборка исходного сообщения:

1. При отсутствии ошибки из принятого сообщения собирается исходное данное .

2. При наличии одной ошибки:

- собирается исходное сообщение

;

- для синдромов S_I3, S_I2, S_I1, S_I0, S_J3, S_J2, S_J1, S_J0 в таблице приведены идентификаторы ошибок:

Для синдромов S_I3, S_I2, S_I1, S_I0, S_J3, S_J2, S_J1, S_J0 рассчитывается идентификатор ошибки, который является номером N ошибочного бита данного:

N = 4∙K_I + K_J = 4∙ log₂ (W_I) + log₂ (W_J),

где W_I - вес синдромов строк S_I3, S_I2, S_I1, S_I0; W_J - вес синдромов столбцов S_J3, S_J2, S_J1, S_J0.

Например. Рассчитать номер ошибочного бита N для синдрома строк S_I3S_I2S_I1S_I0 = 0100₂ = 4₁₀ и синдрома столбцов S_J3S_J2S_J1S_J0 = 0001₂ = 1₁₀:

N = 4∙ log₂ (4₁₀) + log₂ (1₁₀) = 4∙ 2 + 0 = 8.

Получаем ошибку в восьмом бите . Местонахождения ошибочного бита показано в таблице.

Фрагмент 3 (строка I3)

Фрагмент 2 (строка I2)

Фрагмент 1 (строка I1)

Фрагмент 0 (строка I0)

J3

J 2

J 1

J 0

J3

J 2

J 1

J 0

J3

J 2

J 1

J 0

J3

J 2

J 1

J 0

Пример. Применить двухмерный контроль паритета для исходного сообщения 0001 0010 0100 1100.

Кодирование данных и передача по линии связи :

1. Сообщение разбивается на четыре фрагмента, для которых вычисляются паритеты четности

2. Передающий узел собирает из фрагментов сообщение 00011 00101 01001 11000 10111 и посылает его по линии связи.

Прием и проверка данных:

1. Приемный узел принимает сообщение 00011 00101 01001 11000.

2. Сообщение разбивается на фрагменты, для которых рассчитываются синдромы 0001 0010 0100 1100

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

3. Исходное сообщение равно 0001 0010 0100 1100.

Прием и проверка данных (с одной ошибкой):

1. Приемный узел принимает сообщение 00011 00101 11001 11000.

2. Сообщение разбивается на фрагменты, для которых рассчитываются синдромы

4. Расчет номера ошибочного бита N для синдрома строк S_I3S_I2S_I1S_I0 = 0010₂ = 2₁₀ и синдрома столбцов S_J3S_J2S_J1S_J0 = 1000₂ = 8₁₀:

N = 4∙ log₂ (2₁₀) + log₂ (8₁₀) = 4∙ 1 + 3 = 7.

Получаем ошибку в восьмом бите .

5. Восстановление данного 0001 0010 1100 1100.

6. Исправление ошибки, выполняется инверсией бита :

0001 0010 100 1100 = 0001 0010 0100 1100.

Код Хемминга

Помехоустойчивое кодирование методом Хемминга позволяет:

- обнаруживать одиночные ошибки;

- исправлять одиночные ошибки.

Метод основан на перекрестном вычислении битов паритета.

Основными свойствами кода Хемминга являются:

- расстояние по Хеммингу;

- минимальное расстояние по Хеммингу;

- вес Хемминга.

Расстоянием по Хеммингу d(x,y) называется число позиций, в которых различаются два n-разрядных кода.

Минимальным расстоянием d^* называется наименьшее из всех расстояний по Хеммингу между различными парами всех n-разрядных кодов.

Весом Хемминга w(x) называется число ненулевых компонент n-разрядного кода.

Пример.Определить расстояние по Хеммингу d(x,y) для кодов х = 0110 и y = 1011:

		Код х
		Сумма по модулю два
		Код y
		Результат

В результате 1101 единицы отражают число позиций, в которых различаются коды 0110 и 1011. Количество единиц равно 1 + 1 + 0 + 1 = 3.

Ответ. Расстояние по Хеммингу d(0110, 1011) = 3.

Пример.Определить минимальное расстояние d^* для кодов 0110, 1011, 1101:

d(0110, 1011) = 3;

d(1011, 1101) = 2;

d(0110, 1101) = 2.

Ответ. Минимальное расстояние d^* = 2.

Пример.Определить вес Хемминга w(x) для кода х = 0110.

Ответ. Вес Хемминга w(0110) = 0 + 1 + 1 + 0 = 2.

Помехоустойчивые коды характеризуется выражениями:

(n, k, d) или (n, k),

где n – общее число разрядов в передаваемом сообщении; k – число информационных разрядов (k = n - r); r – число проверочных разрядов; d^* – минимальное кодовое расстояние между разрешенными кодовыми комбинациями.

Дополнительным показателями избыточности являются:

- относительная избыточность ;

- относительная скорость передачи .

Рассмотрим работу метода на примере кода Хемминга (7,4) для данного D₃D₂D₁D₀ (n =7, k = 4).

Кодирование данных и передача по линии связи :

1. Вычисление для данного D₃D₂D₁D₀ поверочных битов Р₂Р₁Р₀ по формулам:

Р₀ = D₂ Å D₁ Å D₀;

Р₁ = D₃ Å D₁ Å D₀;

Р₂ = D₃ Å D₂ Å D₀.

2. Переда сообщения D₃D₂D₁D₀Р₂Р₁Р₀ по линии связи.

Прием и проверка данных:

1. Прием сообщения D₃D₂D₁D₀Р₂Р₁Р₀.

2. Вычисление синдромов по формулам:

S₀ = D₂ Å D₁ Å D₀ Å Р₀;

S₁ = D₃ Å D₁ Å D₀ Å Р₁;

S₂ = D₃ Å D₂ Å D₀ Å Р₂.

Трёхразрядный код называется синдромом.

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

3. Проверка на наличие ошибок:

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

Таблица Идентификаторы ошибок

Пример. Передать четырехразрядное данное D₃D₂D₁D₀ = 0000 с контролем достоверности по Хеммингу.

Кодирование данных и передача по линии связи :

1. Вычисление для данного D₃D₂D₁D₀ = 0000 поверочных битов Р₂Р₁Р₀ по формулам:

Р₀ = D₂ Å D₁ Å D₀ = 0 Å 0 Å 0 = 0;

Р₁ = D₃ Å D₁ Å D₀ = 0 Å 0 Å 0 = 0;

Р₂ = D₃ Å D₂ Å D₀ = 0 Å 0 Å 0 = 0.

Поверочные биты Р₂Р₁Р₀ равны 000.

2. Передача сообщения D₃D₂D₁D₀Р₂Р₁Р₀ = 0000 000.

Прием и проверка данных:

1. Прием сообщения D₃D₂D₁D₀Р₂Р₁Р₀ = 0000 000.

2. Вычисление синдромов :

S₀ = D₂ Å D₁ Å D₀ Å Р₀ = 0 Å 0 Å 0 Å 0 = 0;

S₁ = D₃ Å D₁ Å D₀ Å Р₁ = 0 Å 0 Å 0 Å 0 = 0;

S₂ = D₃ Å D₂ Å D₀ Å Р₂ = 0 Å 0 Å 0 Å 0 = 0.

Синдромы равны 000.

3. Проверка на наличие ошибок:

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

Пример. Выполнить верификацию принятого сообщения 0100000, использующее кодирование методом Хемминга (7,4).

Прием и проверка данных:

1. Прием сообщения D₃D₂D₁D₀Р₂Р₁Р₀ = 0100 000.

2. Анализ принятого сообщения:

2. Вычисление синдромов :

S₀ = D₂ Å D₁ Å D₀ Å Р₀ = 1 Å 0 Å 0 Å 0 = 1 Å 0 Å 0 = 1 Å 0 = 1;

S₁ = D₃ Å D₁ Å D₀ Å Р₁ = 0 Å 0 Å 0 Å 0 = 0 Å 0 Å 0 = 0 Å 0 = 0;

S₂ = D₃ Å D₂ Å D₀ Å Р₂ = 0 Å 1 Å 0 Å 0 = 1 Å 0 Å 0 = 1 Å 0 = 1.

3. Проверка на наличие ошибок:

- для синдромов = 101 из таблицы синдромов извлекаем сообщение: «Ошибка в D₂».

4. Исправление ошибки:

- исправление ошибки с помощью логической операции инверсии (второго разряда) = 0000.

Ответ. Передавалось данное 0000.