Корректирующие коды (стр. 3 из 3)
Для обнаружения и исправления ошибки составим аналогичные про-верки на четность контрольных сумм, в соответствии с проверочной матрицей результатом которых является двоичное (n-k) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е, номер ошибочной позиции.
1) k1 Å b3Å b5Å b7= 0Å1Å1Å1 = 1.
2)k2 Å b3Å b6Å b7= 1Å1Å0Å1 = 1.
3) k3 Å b5Å b6Å b7= 0Å1Å0Å1 =0.
Сравнивая синдром ошибки со столбцами проверочной матрицы, определяем номер ошибочного бита. Синдрому 011 соответствует третий столбец, т. е. ошибка в третьем разряде кодовой комбинации. Символ в 3 -й позиции необходимо изменить на обратный.
Пример 2. Построить код Хэмминга для передачи кодовой комбинации 1 1 0 1 1 0 1 1. Показать процесс обнаружения и исправления ошибки в соответствующем разряде кодовой комбинации.
Решение: Рассмотрим алгоритм построения кода для исправления одиночной ошибки.
1. По заданной длине информационного слова (k = 8) , используя соотношения вычислим основные параметры кода n и m.
m = [log2 {(k+1)+ [log2(k+1)]}]=[log2 {(9+1)+ [log2(9+1)]}]=4,
при этом n = k+m = 12, т. е. получили (12, 8)-код.
2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i.
Для рассматриваемой задачи (при n = 12) номера контрольных позиций равны 1, 4, 8.
При этом кодовая комбинация имеет вид:
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12
к1 к2 1 к3 1 0 1 к4 1 0 1 1
3. Определяем значения контрольных разрядов (0 или 1) путем много-кратных проверок кодовой комбинации на четность. Количество проверок равно m = n-k. В каждую проверку включается один контрольный и определенные проверочные биты.
Номера информационных бит, включаемых в каждую проверку определяется по двоичному коду натуральных n-чисел разрядностью - m.
0001 b1 Количество разрядов m - определяет количество прове-
0010 b2 верок.
0011 b3 1) к1Åb3Åb5Åb7Åb9Å а11 = к1Å1Å1Å1Å1Å1 =>
0100 b4 четная при к1=1
0101 b5 2) к2Åb3Åb6Åb7Åb10Åb11= к2Å1Å0Å1Å0Å1 =>
0110 b6 четная при к2=1
0111 b7 3)к3Åb5Åb6Åb7Åb12 = к3Å1Å0Å1Å1=>
1000 b8 четная при к3=1
1001 b9 4) к4Åb9Åb10Åb11Åb12 = к1Å1Å0Å1Å1 =>
1010 b10 четная при к4=1
1011 b11
1100 b12
Передаваемая кодовая комбинация: 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) к1Åb3Åb5Åb7Åb9Åb11 = 1Å1Å0Å1Å1Å1 =1
2) к2Åb3Åb6Åb7Åb10Åb11 = 1Å1Å0Å1Å0Å1 =0
3)к3Åb5Åb6Åb7Åb12 = 1Å0Å0Å1Å1 =1
4) к4Åb9Åb10Åb11Åb12 = 1Å1Å0Å1Å1 =0
Обнаружена ошибка в разряде кодовой комбинации с номером 0101, т. е. в 5 -м разряде. Для исправления ошибки необходимо проинвертировать 5 -й разряд в кодовой комбинации.
Рис. 1. Схема кодера -а и декодера –б для простого (7, 4) кода Хэмминга
Рассмотрим применение кода Хэмминга. В ЭВМ код Хэмминга чаще всего используется для обнаружения и исправления ошибок в ОП, памяти с обнаружением и исправлением ошибок ECCMemory (ErrorCheckingandCorrecting). Код Хэмминга используется как при параллельной, так и при последовательной записи. В ЭВМ значительная часть интенсивности потока ошибок приходится на ОП. Причинами постоянных неисправностей являются отказы ИС, а случайных изменение содержимого ОП за счет флуктуации питающего напряжения, кратковременных помех и излучений. Неисправность может быть в одном бите, линии выборки разряда, слова либо всей ИС. Сбой может возникнуть при формировании кода (параллельного), адреса или данных, поэтому защищать необходимо и то и др. Обычно дешифратор адреса встроен в м/схему и недоступен для потребителя. Наиболее часто ошибки дают ячейки памяти ЗУ, поэтому главным образом защищают записываемые и считываемые данные.
Наибольшее применение в ЗУ нашли коды Хэмминга с dmin=4, исправляющие одиночные ошибки и обнаруживающие двойные.
Проверочные символы записываются либо в основное, либо специальное ЗУ. Для каждого записываемого информационного слова (а не байта, как при контроле по паритету) по определенным правилам вычисляется функция свертки, результат которой разрядностью в несколько бит также записывается в память. Для 16 -ти разрядного информационного слова используется 6 дополнительных бит (32- 7 бит, 64 –8 бит). При считывании информации схема контроля, используя избыточные биты, позволяет обнаружить ошибки различной кратности или исправить одиночную ошибку. Возможны различные варианты поведения системы:
- автоматическое исправление ошибки без уведомления системы;
- исправление однократной ошибки и уведомление системы только о многократных ошибках;
- не исправление ошибки, а только уведомление системы об ошибках;
Модуль памяти со встроенной схемой исправления ошибок –EOS 72/64 (ECConSimm). Аналог микросхема к 555 вж 1 -это 16 разрядная схема с обнаружением и исправлением ошибок (ОИО) по коду Хэмминга (22, 16), использование которой позволяет исправить однократные ошибки и обнаружить все двух кратные ошибки в ЗУ.
Избыточные (контрольные) разряды позволяют обнаружить и исправить ошибки в ЗУ в процессе записи и хранения информации.
В составе ВЖ-1 используются 16 информационных и 6 контрольных разрядов. (DB - информационное слово, CB - контрольное слово).
При записи осуществляется формирование кода, состоящего из 16 информационных и 6 контрольных разрядов, представляющих результат суммирование по модулю 2 восьми информационных разрядов в соответствии с кодом Хэмминга. Сформированные контрольные разряды вместе с информационными поступают на схему и записываются в ЗУ.
