Устройство приняло следующие 7 битные блоки данных

Устройство приняло следующие 7 битные блоки данных

Код Хемминга – это блочный код, позволяющий исправлять одиночные и фиксировать двойные ошибки, разработанный Ричардом Хеммингом в сороковых годах прошлого столетия.

В то время он работал в лаборатории Белла на электромеханической счетной машине Bell Model V. Ввод данных в эту машину осуществлялся с помощью перфокарт. Это была самая ненадежная часть вычислительной машины. Перфокарты часто считывались неправильно. Исправление и обнаружение ошибок ввода данных отнимало огромное количество времени, а пропущенные ошибки могли привести к неверным результатам работы.

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

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

Ричард Хемминг рассчитал минимальное количество проверочных бит, позволяющих однозначно исправлять однократные ошибки.

Если длина информационного блока, который требуется закодировать — m бит. Количество контрольных бит, используемых для его кодирования, – k, то закодированный блок будет иметь длину: n = m+k бит. Для каждого блока такой длины возможны n различных комбинаций, содержащих ошибку.

Таким образом, для каждого передаваемого информационного блока может существовать n–блоков, содержащих однократную ошибку, и один блок — без ошибок. Следовательно, максимальное количество различных закодированных блоков, содержащих не больше одной ошибки, будет: 2 m (n+1), где n = m+k.

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

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

Учитывая, что n = m + k, получаем:

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

Например, для информационных данных длиной 7 необходимо 4 контрольных бита, чтобы обеспечить исправление однократных ошибок, а для данных длинной 128 бит необходимо 8 контрольных бит.

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

Все биты, порядковые номера которых являются степенью двойки, – это контрольные разряды. То есть если порядковый номер бита обозначить символом ‘n’, то для контрольных бит должно быть справедливо равенство: n=2 k , где к – любое положительное целое число.

Например, для закодированной последовательности длиной 13 бит проверочными будут: 1, 2, 4 и 8 биты, так как 2 0 = 1, 2 1 = 2, 2 2 = 4, 2 3 = 8.

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

Для того, чтобы определить какими контрольными битами контролируют бит, необходимо разложить его порядковый номер по степени 2. Таким образом, девятый бит будет контролироваться битами 1 и 8, так как 9 = 2 0 + 2 3 = 1 + 8.

Рассмотрим пример кодирования бинарной последовательности данных, состоящей из семи элементов: 1001101.

1. Определим необходимое количество контрольных разрядов. Расчет будем вести по формуле: k = 2 k – m – 1, где k – количество контрольных разрядов, m – количество информационных разрядов. Так как количество бит должно быть целым числом, то k, вычисленное с помощью этого уравнения, необходимо округлить до ближайшего большего целого числа.

Результат расчета приведен ниже:

Таким образом, число контрольных бит — 4.

2. Определим расположение проверочных бит в результирующей закодированной последовательности. Обозначим информационные биты символом И, а контрольные биты символом П. Индекс около этих символов будет означать их порядковый номер в закодированной последовательности.

Контрольные биты будут занимать четыре позиции с порядковыми номерами, равными степени двойки: 2 0 , 2 1 , 2 2 , 2 3 => 1,2,4,8.

Размещение информационных и контрольных бит в результирующей последовательности будет следующим:

Осталось определить значения проверочных бит.

3. Определим, какие группы контролируют проверочные биты. Для этого разложим порядковые номера информационных бит по степени двойки:

И3: 3 = 2 0 + 2 1 = 1 + 2 => Информационный бит И3 проверяется контрольными битами П1 и П2.

И5: 5 = 2 0 + 2 2 = 1 + 4 => Информационный бит И5 проверяется контрольными битами П1 и П4.

И6: 6 = 2 1 + 2 2 = 2 + 4 => Информационный бит И6 проверяется контрольными битами П2 и П4.

И7: 7 = 2 0 + 2 1 + 2 2 = 1 + 2 + 4 => Информационный бит И7 проверяется контрольными битами П1, П2 и П4.

И9: 9 = 2 0 + 2 3 = 1 + 8 => Информационный бит И9 проверяется контрольными битами П1 и П8.

И10: 10 = 2 1 + 2 3 = 2 + 8 => Информационный бит И10 проверяется контрольными битами П2 и П8.

И11: 11 = 2 0 + 2 1 + 2 3 = 1 + 2 + 8 => Информационный бит И11 проверяется контрольными битами П1, П2 и П8.

4. Рассчитаем значения контрольных бит. Для этого определим группы для всех контрольных бит, просуммируем их по модулю два, а результат запишем в соответствующие контрольные биты (дополним группы до четности единиц):

Таким образом, закодированная последовательность будет иметь следующий вид:

Читайте также:  Какой оператор предоставляет безлимитный интернет

1. Проверим на четность единиц все группы, контролируемые проверочными разрядами:

П1: П1 + И3 + И5 + И7 + И9 + И11 = 0 + 1 + 0 + 1 + 1 + 1 = 0

П2: П2 + И3 + И6 + И7 + И10 + И11 = 1 + 1 + 1 + 1 + 0 + 1 = 1

П4: П4 + И5 + И6 + И7 = 1 + 0 + 1 + 1 = 1

П8: П8 + И9 + И10 + И11 = 0 + 1 + 0 + 1 = 0

Так как проверка четности единиц не прошла для групп контрольных битов П2 и П4, то ошибка содержится в битах, принадлежащих этим группам. Алгоритм Хемминга позволяет исправлять только одну ошибку, поэтому будем искать неисправность, исходя из предположения, что могла произойти только одна ошибка. Если это предположение — неверно, то все попытки исправить данные только привнесут дополнительные искажения информации.

Итак, если ошибка была только одна, то она должна быть в одном из битов, принадлежащих обеим группам. Это биты И6 и И7.

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

Таким образом, очевидно, что ошибка произошла в бите И6, и, инвертировав его значение, мы восстановим принятые данные.

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

Если предположить, что количество ошибок — не более двух, то:

— Данные верны, если во всех контрольных группах количество единиц — четное, и общее количество единиц — тоже четное.

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

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

— Двойная ошибка, если в некоторых контрольных группах количество единиц — нечетное, а общее количество единиц — четное.

Как видите, алгоритм коррекции ошибок Хемминга — достаточно прост и надежен. При этом эффективность кода растет при увеличении информационных блоков. Так, для кодирования 7 бит данных избыточность составляет чуть больше 57%, для кодирования 256 бит избыточность будет 3.5%, а для 1024 – 1%.

Алгоритм кодирования Хэмминга — очень популярен и позволяет значительно повысить надежность передачи и хранения информации. Особенно, он выгоден при кодировании больших блоков данных. Существует большое количество различных способов реализации этого алгоритма.

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

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

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

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

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

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

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

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

. (15 )

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

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

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

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

Двоичные числа и их разряды

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

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

Читайте также:  Файл диспетчера задач 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Передаваемая кодовая комбинация: 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) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е. номер ошибочной позиции.

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

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

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

Наибольшее применение в ЗУ нашли коды Хэмминга с dmin=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 восьми информационных разрядов в соответствии с кодом Хэмминга. Сформированные контрольные разряды вместе с информационными поступают на схему и записываются в ЗУ.

Читайте также:  Семестр обучения это сколько

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

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

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

Рассмотрим (7,4)-код Хемминга, являющийся классической иллюстрацией простейших кодов с исправлением ошибок. Пусть m = (m0, m1, m2, m3) будет тем сообщением, или информационной последовательностью, которую нужно закодировать. Порождающая матрица G для (7, 4)-кода Хемминга имеет вид

Тогда символы соответствующего кодового слова определяются следующим образом :

Например, пусть m = ( 1 0 1 1 ) , тогда соответствующее кодовое слово будет иметь вид U = ( 1 0 1 1 1 0 0 ). Или другой пример: пусть m = ( 1 0 0 0 ), тогда U = ( 1 0 0 0 1 1 0 ).

На основании порождающей матрицы G(7,4) легко реализовать схему кодирования для рассматриваемого (7,4)-кода Хемминга (рис. 3.4).

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

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

Прежде чем говорить об обнаружении и исправлении ошибок корректирующими кодами, напомним само понятие ошибки и методы их описания. Пусть U = ( U0 , U1 ,… Un ) является кодовым словом, переданным по каналу с помехами, а r = ( r0 , r1 , . rn ) — принятой последовательностью, возможно, отличающейся от переданного кодового слова U. Отличие r от U состоит в том, что некоторые символы ri принятой последовательности могут отличаться от соответствующих символов Ui переданного кодового слова. Например, U = ( 0 0 0 1 0 0 0 ) , а r = ( 0 0 0 0 0 0 0) , то есть произошла ошибка в четвертом символе кодового слова, 1 перешла в 0 . Или другой пример: передано кодовое слово U = ( 0 0 1 1 1 1 ), а принятая последовательность имеет вид r = ( 1 0 1 1 1 1 1), то есть ошибка возникла в первом бите кодового слова, при этом 0 перешел в единицу.

Для описания возникающих в канале ошибок Коржик В.И. и др. Расчет помехоустойчивости систем передачи дискретных сообщений. — М.: Радио и связь, 1981. — С. 87 — 99. используют вектор ошибки, обычно обозначаемый как e и представляющий собой двоичную последовательность длиной n с единицами в тех позициях, в которых произошли ошибки. Так, вектор ошибки e = ( 0 0 0 1 0 0 0 ) означает однократную ошибку в четвертой позиции (четвертом бите), вектор ошибки e = ( 1 1 0 0 0 0 0 ) — двойную ошибку в первом и втором битах и т.д.

Тогда при передаче кодового слова U по каналу с ошибками принятая последовательность r будет иметь вид

Приняв вектор r , декодер сначала должен определить, имеются ли в принятой последовательности ошибки. Если ошибки есть, то он должен выполнить действия по их исправлению.

Чтобы проверить, является ли принятый вектор кодовым словом, декодер вычисляет (n-k)-последовательность, определяемую следующим образом:

Здесь НТ — проверочная матрица. При этом r является кодовым словом тогда, и только тогда, когда S = (00..0), и не является кодовым словом данного кода, если S ненулевой. Следовательно, S используется для обнаружения ошибок, ненулевое значение S служит признаком наличия ошибок в принятой последовательности. Поэтому вектор S называется синдромом принятого вектора r.

Некоторые сочетания ошибок, используя синдром, обнаружить невозможно Тепляков И.П., Рощин Б.В. Радиосистемы передачи информации. — М.: Радио и связь, 1982. — С. 201.. Например, если переданное кодовое слово U под влиянием помех превратилось в другое действительное кодовое слово V этого же кода, то синдром равен 0 . В этом случае декодер ошибки не обнаружит и, естественно, не попытается ее исправить. Сочетания ошибок такого типа называются необнаруживаемыми. При построении кодов необходимо стремиться к тому, чтобы они обнаруживали наиболее вероятные сочетания ошибок.

Для рассматриваемого линейного блочного систематического (7,4)-кода Хемминга синдром определяется следующим образом:

пусть принят вектор r = ( r0 , r1 , r2 , r3 , r4 , r5 , r6), тогда

Основываясь на полученных соотношениях, можно легко организовать схему для вычисления синдрома. Для (7,4)-кода Хемминга она приведена на рис. 3. 5.

Покажем теперь, как можно использовать синдром принятого вектора не только для обнаружения, но и для исправления ошибок.

Пусть U = ( U0 , U1 , …, Un-1 ), e = ( е0 , е1, …, еn-1) и r = ( r0 , r1, r2 , …, rn-1) являются передаваемым кодовым словом, вектором-ошибкой и принятым вектором соответственно.

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

Таким образом, синдром принятой последовательности r зависит только от ошибки, имеющей место в этой последовательности, и совершенно не зависит от переданного кодового слова. Задача декодера, используя эту зависимость, определить элементы (координаты) вектора ошибок. Найдя вектор ошибки можно восстановить кодовое слово.

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

Найдем значения синдрома для всех возможных одиночных ошибок в последовательности из семи символов. Все возможные для (7, 4)-кода одиночные ошибки и соответствующие им векторы синдрома приведены в табл. 3. 1.

Ссылка на основную публикацию
Adblock detector