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

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

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 столбца.

	J 3	J 2	J 1	J 0
I 3
I 2
I 1
I 0

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

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

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

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

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

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

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

	J 3	J 2	J 1	J 0	PI
I 3					РI 3
I 2					РI 2
I 1					РI 1
I 0					РI 0
PJ	РJ 3	РJ 2	РJ 1	РJ 0

где Р_{I 3}, Р_{I 2}, Р_I2 , Р_I0 - паритеты строк; Р_{J 3}, Р_{J 2}, Р_{J 1}, Р_{J 0} - паритеты столбцов.

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

	J 3	J 2	J 1	J 0	PI
I 3					РI 3
I 2					РI 2
I 1					РI 1
I 0					РI 0
PJ	РJ 3	РJ 2	РJ 1	РJ 0	РIJ

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

Р_{I 3} Р_{I 2} Р_I2 Р_I0 Р_{J 3} Р_{J 2} Р_{J 1} Р_{J 0} Р_IJ.

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

Р_{I 3} Р_{I 2} Р_I2 Р_I0 Р_{J 3} Р_{J 2} Р_{J 1} Р_{J 0} Р_IJ.

.

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

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

Р_{I 3} Р_{I 2} Р_I2 Р_I0 Р_{J 3} Р_{J 2} Р_{J 1} Р_{J 0} Р_IJ.

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

		J 3	J 2	J 1	J 0	PI
	I 3					РI 3
	I 2					РI 2
	I 1					РI 1
	I 0					РI 0
	PJ	РJ 3	РJ 2	РJ 1	РJ 0	РIJ

3. Для каждой строки вычисляются синдромы S_{I 3}, S_{I 2}, S_{I 1}, S_{I 0}, S_Р. Для каждого столбца вычисляются синдромы S_{J 3}, S_{J 2}, S_{J 1}, S_{J 0}, S_Р

	J 3	J 2	J 1	J 0	PI	SI
I 3					РI 3	SI 3
I 2					РI 2	SI 2
I 1					РI 1	SI 1
I 0					РI 0	SI 0
PJ	РJ 3	РJ 2	РJ 1	РJ 0	РIJ	SРIJ
SJ	SJ 3	SJ 2	SJ 1	SJ 0	SРJI

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

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

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

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

	J 3	J 2	J 1	J 0	PI	SI
I 3					РI 3	SI 3
I 2					РI 2	SI 2
I 1					РI 1	SI 1
I 0					РI 0	SI 0
PJ	РJ 3	РJ 2	РJ 1	РJ 0	РIJ	SРIJ
SJ	SJ 3	SJ 2	SJ 1	SJ 0	SРJI

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

Например, если синдромы строк S_{I 2} = 1, S_{I 0}= 1 и столбцов S_{J 3} = 1, Р_{J 0} =1, то на пересечении строк I ₂, I ₀ и столбцов J ₃, J ₀ находятся биты , D₈, , ,которые не могут быть идентифицированы, а поэтому и исправлены.

	J 3	J 2	J 1	J 0	PI	SI
I 3					РI 3	SI 3
I 2					РI 2	SI 2
I 1					РI 1	SI 1
I 0					РI 0	SI 0
PJ	РJ 3	РJ 2	РJ 1	РJ 0	РIJ	SРIJ
SJ	SJ 3	SJ 2	SJ 1	SJ 0	SРJI

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

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

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

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

;

- для синдромов S_{I 3}, S_{I 2}, S_{I 1}, S_{I 0}, S_{J 3}, S_{J 2}, S_{J 1}, S_{J 0} в таблице приведены идентификаторы ошибок:

Для синдромов S_{I 3}, S_{I 2}, S_{I 1}, S_{I 0}, S_{J 3}, S_{J 2}, S_{J 1}, S_{J 0} рассчитывается идентификатор ошибки, который является номером N ошибочного бита данного:

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

где W_I - вес синдромов строк S_{I 3}, S_{I 2}, S_{I 1}, S_{I 0}; W_J - вес синдромов столбцов S_{J 3}, S_{J 2}, S_{J 1}, S_{J 0}.

Например. Рассчитать номер ошибочного бита N для синдрома строк S_{I 3} S_{I 2} S_{I 1} S_{I 0} = 0100₂ = 4₁₀ и синдрома столбцов S_{J 3} S_{J 2} S_{J 1} S_{J 0} = 0001₂ = 1₁₀:

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

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

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

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

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

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

J 3

J 2

J 1

J 0

J 3

J 2

J 1

J 0

J 3

J 2

J 1

J 0

J 3

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_{I 3} S_{I 2} S_{I 1} S_{I 0} = 0010₂ = 2₁₀ и синдрома столбцов S_{J 3} S_{J 2} S_{J 1} S_{J 0} = 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.

Поиск по сайту: