Определим комбинации корректирующего кода

2. Определим комбинации корректирующего кода.

Для заданного числа информационных разрядов k = 4,число кодовых комбинаций равно N = 2^k = 2⁴ = 16.

1) 0000 5) 0010 9) 0001 13) 0011

2) 1000 6) 1010 10) 1001 14) 1011

3) 0100 7) 0110 11) 0101 15) 0111

4) 1100 8) 1110 12) 1101 16) 1111

Старшинство разрядов принимаем слева на право, в соответствии с их поступлением на вход декодера.

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

Например, для информационного слова I= [1001] кодовое слово имеет вид

.

Передаваемые в канал кодовые комбинации имеют вид:

1) 0000 000 5) 0010 110 9) 0001 101 13) 0011 011

2) 1000 111 6) 1010 001 10) 1001 010 14) 1011 100

3) 0100 011 7) 0110 101 11) 0101 110 15) 0111 000

4) 1100 100 8) 1110 010 12) 1101 101 16) 1111 111

Процесс декодирования состоит в определении соответствия принятого кодового слова, переданному информационному и осуществляется с помощью проверочной матрицы H(7, 4).

Для построенного (7, 4)-кода проверочная матрица имеет вид

.

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

Пусть в процессе передачи произошла ошибка во 2-м информационном разряде 1 1 0 1 1 0 0 1

В соответствии с проверочной матрицей составляем проверочные векторы

 

p₁Åa₁Åa₂Åa₄ =S₁ = 0Å1Å1Å0 = 0;

p₂Åa₁Åa₂Åa₃ =S₂ = 0Å1Å1Å1 = 1 ;

p₃Åa₁Åa₃Åa₄ =S₃ = 1Å1Å0Å1 = 1.

Синдром 011 показывает, что ошибка произошла во 2-м информационном разряде, который необходимо проинвертировать.

 

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

 

Решение: Объем кода равен N = 2^k. При 100 сообщениях: 100 £ N £ 2^k , откуда k = 7. По заданной длине информационного слова, используя соотношения:

n = k+m, 2ⁿ ³ (n+1)2^k и 2^m ³ n+1

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

 

m=[log₂ {(k+1)+ [log₂(k+1)]}]=[log₂ {(7+1)+ [log₂(7+1)]}]=4.

Откуда n = 11, т. е. получили (11, 7)-код.

В качестве информационной матрицы выбираем единичную матрицу I(7x7).Проверочная матрица содержит 4 столбца и 7 строк, которые содержат r₁ £ d₀-1 единиц в четырехразрядном коде (2, 3, 4-единицы).

.

3. КОД ХЭММИНГА

 

Код Хэмминга относится к классу линейных кодов и представляет собой систематический код – код, в котором информационные и контрольные биты расположены на строго определенных местах в кодовой комбинации.

Код Хэмминга, как и любой (n, k)- код, содержит к информационных и m = n-k избыточных (проверочных) бит.

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

Существуют различные методы реализации кода Хэмминга и кодов которые являются модификацией кода Хэмминга. Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданному количеству информационных символов - k, либо информационных комбинаций N = 2^k , используя соотношения:

 

n = k+m, 2ⁿ ³ (n+1)2^k и 2^m ³ n+1 (14)

m = [log₂ {(k+1)+ [log₂(k+1)]}]

вычисляют основные параметры кода n и m.

2. Определяем рабочие и контрольные позиции кодовой комбинации. Номера контрольных позиций определяются по закону 2ⁱ,где i=1, 2, 3,... т.е. они равны 1, 2, 4, 8, 16,… а остальные позиции являются рабочими.

3. Определяем значения контрольных разрядов (0 или 1 ) при помощи многократных проверок кодовой комбинации на четность. Количество проверок равно m = n-k. В каждую проверку включается один контро-льный и определенные проверочные биты. Если результат проверки дает четное число, то контрольному биту присваивается значение -0, в противном случае - 1. Номера информационных бит, включаемых в каждую проверку, определяются по двоичному коду натуральных n –чисел разрядностью – m (табл. 1, для m = 4) или при помощи проверочной матрицы H(m´n), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до 2^k –1 перечисленных в возрастающем порядке. Для m = 3 проверочная матрица имеет вид

 . (15 )

Количество разрядов m - определяет количество проверок.

В первую проверку включают коэффициенты, содержащие 1 в младшем (первом) разряде, т. е. b₁, b₃, b₅ и т. д.

 Во вторую проверку включают коэффициенты, содержащие 1 во втором разряде, т. е. b₂, b₃, b₆ и т. д.

 В третью проверку - коэффициенты которые содержат 1 в третьем разряде и т. д.

Таблица 1

Десятичные числа (номера разрядов кодовой комбинации)	Двоичные числа и их разряды
	3	2	1
1  2  3  4  5  6  7	0  0  0  1  1  1  1	0  1  1  0  0  1  1	1  0  1  0  1  0  1

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

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

Схема кодера и декодера для кода Хэмминга приведена на рис. 1.

Пример 1. Построить код Хемминга для передачи сообщений в виде последовательности десятичных цифр, представленных в виде 4 –х разрярных двоичных слов. Показать процесс кодирования, декодирования и исправления одиночной ошибки на примере информационного слова 0101.

Решение:

1. По заданной длине информационного слова (k = 4), определим количество контрольных разрядов m, используя соотношение:

 

m = [log₂ {(k+1)+ [log₂(k+1)]}]=[log₂ {(4+1)+ [log₂(4+1)]}]=3,

при этом n = k+m = 7, т. е. получили (7, 4) -код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2ⁱ.

Для рассматриваемой задачи (при n = 7) номера контрольных позиций равны 1, 2, 4. При этом кодовая комбинация имеет вид:

b₁ b₂ b₃ b₄ b₅ b₆ b₇

к₁ к₂ 0 к₃ 1 0 1

3. Определяем значения контрольных разрядов (0 или 1), используя проверочную матрицу (5).

Первая проверка:

 k₁ Å b₃Å b₅Å b₇ = k₁Å0Å1Å1 будет четной при k₁ = 0.

Вторая проверка:

 k₂ Å b₃Å b₆Å b₇ = k₂Å0Å0Å1 будет четной при k₂ = 1.

Третья проверка:

 k₃ Å b₅Å b₆Å b₇ = k₃Å1Å0Å1 будет четной при k₃ = 0.

1 2 3 4 5 6 7

Передаваемая кодовая комбинация: 0 1 0 0 1 0 1

Допустим принято: 0 1 1 0 1 0 1

 

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

1) k₁ Å b₃Å b₅Å b₇ = 0Å1Å1Å1 = 1.

2) k₂ Å b₃Å b₆Å b₇ = 1Å1Å0Å1 = 1.

3)         k₃ Å b₅Å b₆Å b₇ = 0Å1Å0Å1 = 0.

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

Пример 2. Построить код Хэмминга для передачи кодовой комбинации 1 1 0 1 1 0 1 1. Показать процесс обнаружения и исправления ошибки в соответствующем разряде кодовой комбинации.

 

Решение: Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданной длине информационного слова (k = 8) , используя соотношения вычислим основные параметры кода n и m.

 

m = [log₂ {(k+1)+ [log₂(k+1)]}]=[log₂ {(9+1)+ [log₂(9+1)]}]=4,

при этом n = k+m = 12, т. е. получили (12, 8)-код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2ⁱ.

Для рассматриваемой задачи (при n = 12) номера контрольных позиций равны 1, 4, 8.

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

b₁ b₂ b₃ b₄ b₅ b₆ b₇ b₈ b₉ b₁₀ b₁₁ b₁₂

к₁ к₂ 1 к₃ 1 0 1 к₄ 1 0 1 1

3. Определяем значения контрольных разрядов (0 или 1) путем много-кратных проверок кодовой комбинации на четность. Количество проверок равно m = n-k. В каждую проверку включается один контрольный и определенные проверочные биты.

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

0001 b₁ Количество разрядов m - определяет количество прове-

0010 b₂ верок.

0011 b₃ 1) к₁Å b₃ Å b₅Å b₇Å b₉Å а₁₁ = к₁Å1Å1Å1Å1Å1 =>

0100 b₄ четная при к₁=1

0101 b₅ 2) к₂Å b₃Å b₆Å b₇Å b₁₀Å b₁₁= к₂Å1Å0Å1Å0Å1 =>

0110 b₆ четная при к₂=1

0111 b₇ 3)к₃Å b₅Å b₆Å b₇Å b₁₂ = к₃Å1Å0Å1Å1=>

1000 b₈ четная при к₃=1

1001 b₉ 4) к₄Å b₉Å b₁₀Å b₁₁Å b₁₂ = к₁Å1Å0Å1Å1 =>

1010 b₁₀ четная при к₄=1

1011 b₁₁

1100 b₁₂

 

 Передаваемая кодовая комбинация: 1 2 3 4 5 6 7 8 9 10 11 12

1 1 1 1 1 0 1 1 1 0 1 1

Допустим, принято: 1 1 1 1 0 0 1 1 1 0 1 1

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

1) к₁Å b₃Å b₅Å b₇Å b₉Å b₁₁ = 1Å1Å0Å1Å1Å1 =1

2) к₂Å b₃Å b₆Å b₇Å b₁₀Å b₁₁ = 1Å1Å0Å1Å0Å1 =0

3)к₃Å b₅Å b₆Å b₇Å b₁₂ = 1Å0Å0Å1Å1 =1

4) к₄Å b₉Å b₁₀Å b₁₁Å b₁₂ = 1Å1Å0Å1Å1 =0

Обнаружена ошибка в разряде кодовой комбинации с номером 0101, т. е. в 5 -м разряде. Для исправления ошибки необходимо проинвертировать 5 -й разряд в кодовой комбинации.

Рис. 1. Схема кодера -а и декодера –б для простого (7, 4) кода Хэмминга

Рассмотрим применение кода Хэмминга. В ЭВМ код Хэмминга чаще всего используется для обнаружения и исправления ошибок в ОП, памяти с обнаружением и исправлением ошибок ECC Memory (Error Checking and Correcting). Код Хэмминга используется как при параллельной, так и при последовательной записи. В ЭВМ значительная часть интенсивности потока ошибок приходится на ОП. Причинами постоянных неисправностей являются отказы ИС, а случайных изменение содержимого ОП за счет флуктуации питающего напряжения, кратковременных помех и излучений. Неисправность может быть в одном бите, линии выборки разряда, слова либо всей ИС. Сбой может возникнуть при формировании кода (параллельного), адреса или данных, поэтому защищать необходимо и то и др. Обычно дешифратор адреса встроен в м/схему и недоступен для потребителя. Наиболее часто ошибки дают ячейки памяти ЗУ, поэтому главным образом защищают записываемые и считываемые данные.

Наибольшее применение в ЗУ нашли коды Хэмминга с d_min=4, исправляющие одиночные ошибки и обнаруживающие двойные.

Проверочные символы записываются либо в основное, либо специальное ЗУ. Для каждого записываемого информационного слова (а не байта, как при контроле по паритету) по определенным правилам вычисляется функция свертки, результат которой разрядностью в несколько бит также записывается в память. Для 16 -ти разрядного информационного слова используется 6 дополнительных бит (32- 7 бит, 64 –8 бит). При считывании информации схема контроля, используя избыточные биты, позволяет обнаружить ошибки различной кратности или исправить одиночную ошибку. Возможны различные варианты поведения системы:

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

- исправление однократной ошибки и уведомление системы только о многократных ошибках;

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

Модуль памяти со встроенной схемой исправления ошибок –EOS 72/64 (ECC on Simm). Аналог микросхема к 555 вж 1 -это 16 разрядная схема с обнаружением и исправлением ошибок (ОИО) по коду Хэмминга (22, 16), использование которой позволяет исправить однократные ошибки и обнаружить все двух кратные ошибки в ЗУ.

Избыточные (контрольные) разряды позволяют обнаружить и исправить ошибки в ЗУ в процессе записи и хранения информации.

В составе ВЖ-1 используются 16 информационных и 6 контрольных разрядов. (DB - информационное слово, CB - контрольное слово).

При записи осуществляется формирование кода, состоящего из 16 информационных и 6 контрольных разрядов, представляющих результат суммирование по модулю 2 восьми информационных разрядов в соответствии с кодом Хэмминга. Сформированные контрольные разряды вместе с информационными поступают на схему и записываются в ЗУ.

	(22,16)

 

4 схе(72,64)

 

Рис.2. Схема контроля

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

Любая однократная ошибка в 16 разрядном слове данных изменяет 3 байта в 6 разрядном контрольном слове. Обнаруженный ошибочный бит инвертируется.

Список Литературы

1.         Гриценко В.М, Недвоичные арифметические корректирующие коды, Пробл. передачи информ., 5:4 (1969), 19–27

2.         Злотник Б.М. Помехоустойчивые коды в системах связи.—M.: Радио и связь, 1989.—232 c.

3.         Кловский Д.Д. Теория передачи сигналов. –М.: Связь, 1984.

4.         Ковалгин Ю.А., Вологдин Э. И. Цифровое кодирование звуковых сигналов. Издательство: Корона-Принт, 2004. – 240с.

5.         Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 2006.

6.         Микропроцессорные кодеры и декодеры/В.М. Муттер, Г.А. Петров и др.—М.: Радио и связь, 1991.—184 с.

7.         Питерсон У., Коды, исправляющие ошибки, пер. с англ., М., 1964.

8.         Семенюк В.В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001