Hamming Code Simulator

 

Систематический код, предложенный в 1949 г. американским учёным Ричардом Хэммингом, обладает способностью не только обнаруживать, но и исправлять одиночные ошибки.

Рассмотрим принцип построения кода Хэмминга с минимальным кодовым расстоянием d= 3, т.е. способностью обнаруживать место появления любой однократной ошибки. Построение кода состоит в разбиении разрядов слова на взаимно пересекающиеся подмножества, причём каждому подмножеству ставится в соответствие один контрольный разряд проверки на чётность. Количество контрольных разрядов кода Хэмминга определяется из следующего соотношения:

2k-1 ³ m+k > 2k-1.

Контрольные разряды перемежаются с информационными и располагаются в позициях с номерами Nk=2i (i = 0, 1, 2, …), т.е. в позициях с номерами 1, 2, 4, 8, 16 и т.д.

Формирование подмножеств производится на основе анализа номера разряда при записи его в двоичной системе счисления. Все разряды кодового слова, имеющие единицу в первом (младшем) разряде своего номера, включаются в первое подмножество, во втором — во второе и т.д. Затем подсчитывается количество единиц в разрядах, относящихся к каждому подмножеству, и в соответствующий контрольный разряд записывается единица, если это количество нечётно, и ноль — если чётно.

В табл.16.2 иллюстрируется разбиение разрядов на указанные выше подмножества для 15-разрядного кодового слова, состоящего из 11 информационных разрядов и 4 контрольных.

 

Таблица 16.2
Номер разрядов кодового слова Подмножество
десятичный двоичный
*      
  *    
* *    
    *  
*   *  
  * *  
* * *  
      *
*     *
  *   *
* *   *
    * *
*   * *
  * * *
* * * *

 

Пример кодирования 11-разрядного информационного слова А = 10111010111 представлен на рис.16.5.

 
 

Рис.16.5. Кодирование информационного слова по Хэммингу

 

 

При декодировании (процесс обнаружения ошибки) вычисляется синдром ошибки S = sk sk-1 … s2 s1 , по которому можно судить о наличии ошибки и её месте. Число разрядов в синдроме ошибки равно числу контрольных разрядов кода Хэмминга для данного слова. В рассматриваемом случае будем иметь четырёхразрядный синдром ошибки S = s4 s3 s2 s1 . Для вычисления разрядов синдрома ошибки si нужно сложить по модулю 2 разряды, относящиеся к i-му подмножеству, включая i-й контрольный разряд кода Хэмминга. Если все разряды синдрома ошибки равны нулю S = 0 0 0 0, то это свидетельствует о том, что в закодированном слове ошибки отсутствуют. Если синдром не равен нулю, значит в слове имеется ошибка, а значение синдрома указывает на ошибочный разряд.

Например, ошибка произошла в пятом справа разряде закодированного слова, причём первым считается крайний правый разряд. Это приведёт к нарушению чётности единиц в первом и третьем подмножествах. Следовательно, разряды синдрома ошибки будут равны: s4 = 0, s3 = 1, s2 = 0, s1 = 1. Синдром ошибки S = 0101 указывает на пятый разряд. Для исправления ошибки достаточно проинвертировать значение указанного разряда.

Однако если в закодированном слове будет присутствовать ошибка кратности 2 или более, синдром ошибки укажет на разряд, не содержащий ошибки.

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

Если произойдёт одиночная ошибка, то её выявит проверка на чётность всего слова, а место ошибки определится синдромом ошибки. При искажении содержимого двух разрядов общая проверка на чётность ошибку не зафиксирует, но синдром ошибки будет отличен от нуля. Это указывает на то, что ошибка есть, хотя определить её место становится уже невозможным. Ошибки кратности 3, 5, 7, … будут восприниматься как одиночная ошибка. Однако ввиду того, что код Хэмминга используется в основном для контроля полупроводниковых ЗУ, в которых наиболее вероятными являются одиночные ошибки (с увеличением кратности ошибки на единицу вероятность её появления уменьшается примерно на порядок), данный недостаток кода можно считать несущественным.

В табл.16.3 показаны варианты решений, принимаемых при декодировании модифицированного кода Хэмминга.

 

Таблица 16.3
Общая чётность Синдром ошибки Решение
= 0 = 0 Ошибки нет
= 0 ¹ 0 Неисправимая ошибка кратности 2, 4, 6, 8, …
¹ 0 = 0 Неисправимая пакетная ошибка кратности 2i-1, где i = 2, 3, 4, … , располагающаяся в 2i-1 младших разрядах закодированного слова
¹ 0 ¹ 0 Ошибка кратности 1, 3, 5, 7, … . Поскольку вероятность появления тройной ошибки в 100 раз меньше, чем вероятность появления однобитовой ошибки, решаем, что произошла одиночная ошибка

 

По методу Хэмминга могут быть построены коды различной длины. При этом, чем больше длина кода, тем меньше относительная избыточность. Например, для контроля числа, имеющего 56 двоичных разрядов, потребуется только шесть контрольных разрядов кода Хэмминга. Коды Хэмминга используют в основном для контроля полупроводниковых ЗУ и контроля передачи информации по каналам связи. При контроле ЗУ их надёжность увеличивается в 60 — 85 раз [5, 23].

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

 

 

Calculating the Hamming Code

The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error. Create the code word as follows:

  1. Mark all bit positions that are powers of two as parity bits.

    Код Хемминга онлайн Hamming online

    (positions 1, 2, 4, 8, 16, 32, 64, etc.)

  2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
  3. Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
    Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,…)
    Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,…)
    Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,…)
    Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,…)
    Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,…)
    Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,…)
    etc.
  4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

Here is an example:

A byte of data: 10011010
Create the data word, leaving spaces for the parity bits: _ _ 1 _ 0 0 1 _ 1 0 1 0
Calculate the parity for each parity bit (a ? represents the bit position being set):

  • Position 1 checks bits 1,3,5,7,9,11: _ _ 0 _ 0 0. Even parity so set position 1 to a 0: _ _ 0 _ 0 0
  • Position 2 checks bits 2,3,6,7,10,11:
    0 _ 0 _ 1 0. Odd parity so set position 2 to a 1: 0 _ 0 _ 1 0
  • Position 4 checks bits 4,5,6,7,12:
    0 1 1 _ 1 0 1 . Odd parity so set position 4 to a 1: 0 1 1 _ 1 0 1
  • Position 8 checks bits 8,9,10,11,12:
    0 1 1 1 0 0 1 . Even parity so set position 8 to a 0: 0 1 1 1 0 0 1
  • Code word: 011100101010.

Finding and fixing a bad bit

The above example created a code word of 011100101010. Suppose the word that was received was 011100101110 instead. Then the receiver could calculate which bit was wrong and correct it. The method is to verify each check bit. Write down all the incorrect parity bits. Doing so, you will discover that parity bits 2 and 8 are incorrect. It is not an accident that 2 + 8 = 10, and that bit position 10 is the location of the bad bit. In general, check each parity bit, and add the positions that are wrong, this will give you the location of the bad bit.

Try one yourself

Test if these code words are correct, assuming they were created using an even parity Hamming Code . If one is incorrect, indicate what the correct code word should have been. Also, indicate what the original data was.

  • 010101100011
  • 111110001100
  • 000010001010

Calculating the Hamming Code

Теоретическая часть

Программа предназначена для численного решения системы обыкновенных дифференциальных уравнений вида:

Y'=F(X,Y), с начальными условиями Y(X0)=Yo на отрезке [X,X] методом Хемминга с постоянным шагом интегрирования. В каждой i+1 точке находим начальное приближение Р к решению Y по предсказывающей формуле:

Pi+1=Yi-3+4*h*(2*Y'i-Y'i-1+2*Y'i-2)/3, где

Yi-3 решение в i-3 точке,

Y'i,Y'i-1,Y'i-2 — значения производных в точках i, i-1,i-2 соответственно.

Для улучшения решения используется корректирующая формула

Ci+1=[9*Yi-Yi-2+3*h*(M'i+1+2*Y'i-Y'i-1)]/8, где

Mi+1=Pi+1-112*(P-Ci)/121; M'i+1=F(Xi+1,Mi+1).

Решение системы в i+1 точке находится по формуле

G=Wj*|Pi+1,j-Ci+1|, где

Wj=1

j- номер компоненты вектора.

На участке "разгона" значения Yi-k и Y'i-k (k=0, 1, 2)вычисляются методом Рунге-Кутта по формуле Yi=Ui(2)-(Ui(i)-Ui(2))/15, где i- номер точки, в которой ищется решение, Ui- решение системы в i-ой точке, полученное с шагом h/l;

U(l)i-m+1/l=A(l)i-m+(K(l)1+2*K(l)2+2*K(l)3+K(l)4)i—m+1/l/6, где

j=1, 2, …, n,

K(l)1=h*F(Xi-m,A(l)i-m)/l;

K(l)2=h*F(Xi-m+h/2*l,A(l)i-m+K(l)1/2)/l;

K(l)3=h*F(Xi-m+h/2*l,A(l)i-m+K(l)2/2)/l;

K(l)4=h*F(Xi-m+h/l,A(l)i-m+K(l)3)/l.

A, U ,K — векторы n-го порядка; l=1, 2; m=1 при l=1; m=1,1/2 при l=2;

A(l)i-1=Y(l)i-1; A(2)i-1/2=U(2)i-1/2.

Характеристика программы.

Программа состоит из стандартной информативы, реализующей описанный метод, рабочей информативы, задающей правые части уравнений системы и директивы.

Длина стандартной информативы 1600 символов. Объем исходных данных : 7 чисел, 2 массива, n функций. В результате работы программы на печать выводится на участке "разгона" X, значения функций и производных, далее X, G и Y[n] на всем отрезке интегрирования через Ю шагов и в конце отрезка.

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

"Разгон" (нахождение значений функций и производных в точках X0, X0+Q, X0+2*Q , X0+3*Q, где Q — шаг интегрирования )осуществляется методом Рунге-Кутта с увеличенной разрядностью.

В программе предусмотрена возможность при получении большой погрешности вычисления в точка "разгона" уменьшить шаг интегрирования в этих точках (см. способ задания J), а при быстром возрастании погрешности вычислений G уменьшить шаг интегрирования методом Хемминга или увеличить разрядность вычислений.

Программа позволяет производить интегрирование как с положительным, так и с отрицательным шагом (соответственно меняются X0, Xк и Q).

Порядок решения задачи.

Для решения задачи вводятся стандартная и рабочая информативы и директива.

В рабочей информативе после метки Ц программа вычисления правых частей системы. Здесь Z[1]=…; Z[2]=…; …;Z[n]=…; — правые части исходной системы обыкновенных дифференциальных уравнений как функции от X1 и Y[1], Y[2], …,Y[n], X1 — соответствует аргументу, Y[I] — соответствует функциям. I=1, 2, …, N. Операторная часть рабочей информативы заканчивается оператором перехода "НА" Ф.

В описательной части рабочей информативы задаются X0, XK — соответственно начало и конец отрезка интегрирования, Q -шаг интегрирования методом Хемминга, J — число, определяющее,во сколько раз следует уменьшить шаг интегрирования методом Рунге-Кутта на участке "разгона" для получения решения того же порядка точности, что и в методе Хемминга,

N=n — порядок системы;

Y[n] — вектор начальных условий,

W[n] — вектор коэффициентов для вычисления невязки

W[I]=1, и описаны

A[n], B[n], C[n] — массивы значений функций в точках i-3,

i-2, i-1 соответственно,

Я[n], Б[n], Г[n], D[n] — массивы значений производных в точках i-3, i-2, i-1, i соответственно, Z[n] — массив правых частей,

П[n], P[n] — рабочие массивы.

В директиве задаются : R — разрядность вычислений по методу Хемминга ("разгон" происходит с увеличенной разрядностью), Ю — число, определяющее период печати (количество шагов). Директива должна оканчиваться оператором "НА" HMG.

Описание работы программы

Данная расчетно-графическая работа (далее РГР) составлена на языке PC MathLab ( PC-MATLAB (c) Copyright The MathWorks,Inc. 1984-1989 Version 3.5f 17-July-89 Serial Number 22961) и выполнена в виде двух модулей (третий — контрольный пример),распечатка которых приведена в приложении.

1. Hemming.m

"Стандартный" головной модуль.

Входные данные: отсутствуют.

Выходные данные: отсутствуют.

Язык реализации: PC MathLab.

Операционная система: MS-DOS 3.30 or higher

Пояснения к тексту модуля:

Структура данного модуля элементарна. Вначале очищается экран, задаются исходные данные для второго модуля, как X0,XK — начальное и конечное значение, Q — шаг, J — число, определяющее во сколько раз нужно уменьшать шаг интегрирования методом Рунге-Кутта (далее Р-К) на участке "разгона" для получения того же порядка точности, что и в методе Хемминга, N — порядок системы, Y — вектор начальных значений, W — вектор коэффициентов для вычисления невязки и т.д. Затем вызывается модуль решения системы в формате:

[x,y,dg]=hem('ours',x0,xk,q,j,n,y,w,ur), где

x,y — точки решения

dg — ошибка остальные параметры описаны выше.

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

2. Hem.m

Модуль, которые непосредственно и решает систему ОДУ ме

тодом Хемминга.

Входные данные:

FunFcn — имя функции, вычисляющей левые части

X0,XK — начальное и конечное значение для счета

Q — шаг интегрирования

J — число, определяющее во сколько раз нужно уменьшать шаг интегрирования методом Рунге-Кутта (далее Р-К) на участке "разгона" для получения того же порядка точности, что и в методе Хемминга

N — порядок системы

Y — вектор начальных значений

W — вектор коэффициентов для вычисления невязки

UR — число, определяющее период печати

Выходные данные:

x — матрица точек, для которых вычислено решение

y — матрица решений

dg — ошибка интегрирования

Язык реализации: PC MathLab.

Операционная система: MS-DOS 3.30 or higher

Пояснения к тексту модуля:

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

После описания функции HEM устанавливается формат выходных данных LONG E, а также происходит инициализация рабочих массивов, как массивы значений функции в точках i-3, i-2, i-1;массивы значений производных в этих же точках, массивы правых частей и т.д.

Всвязи с отсутствием в языке MathLab конструкции безусловного перехода, используется конструкции While 1 (бесконечный цикл), Break (переход к началу While) и IF (Если).

Из-за таких немного "странных" конструкций вся дальнейшая часть программы может быть весьма условно представлена такой схемой:

While (не конец расчетов)

While 1

IF

END

IF

END

end

end

В целом, в данных циклах вычисляется номер шага, и если он меньше 5, то вычисления сводятся к вычислению методом Р-К,а если больше 5, то производятся вычисления по методу Хемминга со всеми своими дополнительными действиями, как вычисление по корректирующей формуле и т.д. В обоих случаях происходит обновление рабочих и других промежуточных массивов и вывод информации на экран. В случае решения в точках "разгона" вычисляются также коэффициенты K1, K2, K3, K4, используемые в методе Р-К. Также функция сама проверяет точность вычислений и в случае необходимости корректирует шаг. Если шаг "сделан", то программа выводит результаты на экран и заносит их в массив,который представлен в виде нескольких столбцов. Также в необходимых для функции случаях она обращается к подпрограмме FunFcn, которая занимается вычислением левых частей, вызов и возврат значений которой должен быть следующим:

Z=feval(FunFcn,x,y), где

Z — вектор вычисленных левых частей,

X,Y — векторы точек, для которых производится вычисление.

Для удобства отладки и описания, программа разбита на части, обозначенные русскими заглавными буквами (Ш,Щ,Л и т.д.), которые соответствуют блокам, обозначенным в примере программы, приведенной в задании. Несмотря на то, что приведенная программа написана на условном языке, прокомментировать текст нашей программы на языке MathLab довольно удобно с использованием данных обозначений (Конечно, часть блоков опущена, в связи с отсутствием принципиальной значимости. Кроме того изменен порядок появления блоков в программе):

"Э" — начальное вычисление левых частей.

"Ф" — общий цикл, в котором и происходят собственно все вычисления. Он начинается с конструкций:

While (xk-x1)>0

While 1,

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

Также внутри блока "Ф" происходят вычисления корректирующей формулы IAR(i) а также оценка погрешности вычислений G,если они еще не были рассчитаны на предыдущем шаге.

"Ц" — вычисление левых частей.

"Щ" — на этом этапе происходит перемещение данных в рабочих массивах и X=X+H, то есть происходит переход к следующему шагу. Также на этом этапе происходит вывод на экран и формирование выходных массивов Yout, Xout, DGout.

"Л" — в этом блоке происходит расчет самой предсказывающей формулы метода Хемминга — P(i) и Y(i) и происходит расчет левых частей, т.е. снова в программе появляется блок "Ц".

Затем опять продолжается блок "Ф". Идет проверка на каком шаге мы находимся и, если он (шаг) меньше 5, то идет подготовка к расчету методом Р-К, то есть идет участок "разгона". Соответственно идет расчет коэффициентов K1, K2, K3 и K4, необходимых для метода Р-К. Также внутри данного блока еще раз встречается блок "Ц", в котором происходит расчет левых частей, необходимых для метода Р-К.


Поиск Лекций


Кодирование Хемминга с подсчетом единичных бит

Санкт-Петербургский государственный политехнический университет

Факультет технической кибернетики

—————————

Кафедра информационной безопасности компьютерных систем

ОТЧЕТ

по лабораторной работе №4

«Контроль и восстановление целостности информации»

По курсу «Основы информационной безопасности»

Студент: Виноградова М.М.
  гр. 1088/4
Преподаватель: Калинин М.О.

Санкт-Петербург

1. Цель:

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

 

Теоретические сведения

Помехоустойчивое кодирование

 

Среда, no которой передается информация, He может быть абсолютно надежной. В беспроводных системах связи и телекоммуникационных системах уровень помех бывает очень высоким, Наиболее простой способ проверки целостности передаваемых данных — использование контрольных cyмм. Однако такой подход позволяет только обнаруживать влияние среды. Ha передаваемую информацию. В том случае, если необходимо исправлять ошибки в Переданных данных без их повторной передачи, применяется помехоустойчивое кодирование.

Теория помехоустойчивого кодирования базируется Ha результатах исследований, выполненных шеннона. Теорема шеннона утверждает, что KPH любой производительности источника, меньшей, чем пропускная способность канала, существует такой способ кодирования, который позволяет обеспечить передачу всей информации, создаваемой источником, co сколь угодно малой Вероятностью ошибки.

Все методы помехоустойчивого кодирования обладают общими свойствами: использованием избыточной информации и усреднением шума. Закодированные помехоустойчивые сообщения всегда содержит дополнительные — избыточные — символы, Поэтому помехоустойчивое кодирование также называют избыточным. Дополнительные символы применяют для того, чтобы сделать маловероятной потерю сообщением индивидуальности из-за внесения искажений. Эффект усреднения шума достигается за счет того, что избыточные символы зависят от нескольких значимых информационных символов.

В результате влияния пoмex в сообщении возникают ошибки. Ошибки в сообщении могут быть однобитными или групповыми. У групповых ошибок есть свои позитивные и негативные свойства. Положительное свойство групповой ошибки заключаются в следующем. Пусть данные передаются блоками no 1000 бит, a вероятность ошибки

составляет 0,001 Ha бит. Если ошибки изолированные и независимые, то 63% блоков (0,63~2:1-0,999^(1000)) будут содержать ошибки. Если же они возникают группами по 100 сразу, то ошибки будут содержать 1% блоков (0,01~1-0,999^(10)). Зато, если ошибки нe группируются, То в каждом кадре они невелики, и есть возможность их исправить. Негативное свойство групповых ошибок заключается в том, что они портят кадр безвозвратно. В результате требуется повторная пересылка сообщения, что в некоторых системах невозможно (например, в телефонных сетях).

 

Кодирование Хемминга

 

В помехоустойчивом кодировании вводится понятие расстояния Хемминга — минимального числа разрядов с неодинаковыми значениями кодовых слов. За счет сокращения информационной емкости кодов становится возможным обнаруживать нарушения целостности передаваемой информации. Для исправления одного сбойного бита требуется увеличить расстояние Хемминга до трех.

Калькулятор кодов онлайн.

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

Обнаружив ошибку, декодер последовательно сравнивает искаженный символ co всеми разрешенными символами, стремясь найти символ, наиболее схожий с искаженным (т.е. символ с наименьшим числом различий, a именно нe более чем в d-1 позициях, где d— расстояние Хемминга).

B общем случае, если количество сбойных бит меньше расстояния Хемминга хотя 6ы наполовину, то декодер может гарантированно восстановить исходный символ.

Таким образом, условие обнаружения ошибок: d>=r, где r —

количество ошибок; условие успешного восстановления информации:

d>2r. Поэтому простейшая реализации кодирования Хемминга дополнительно к информационным разрядам вводит L=log2К избыточных контролирующих разрядов, где К — число информационных разрядов. Число L округляется до ближайшего большего целого значения. L‑ разрядный контролирующий код есть инвертированный результат

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

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

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

Биты, номера которых являются степенью 2, являются контрольными, остальные биты — информационными. Каждый контрольный бит отвечает за четность суммы связанной c ним группы бит, расположенных справа. Если сумма соответствующих информационных

битов четная, то контрольный бит равен нулю, и наоборот.

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

 

 

Результаты работы

Кодирование Хемминга с подсчетом единичных бит

 

Создадим файл, на котором будем проверять работоспособность программ

 

 

В результате кодировки получаем фрагмент

Вносим изменения в исходный файл:

 

       
   
 

 

 

 

Получили искажения в файле:

 

Запускаем декодер, восстанавливаем сообщение:

 

3.2. Ответы на контрольные вопросы

©2015-2018 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

Коды Хемминга

 

Они позволяют  не только обнаруживать ошибки, но и исправлять их.

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

  1. Определение количества контрольных разрядов (k).

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

Учитывая, что с помощью k двоичных разрядов можно закодировать 2k состояний, можно получить неравенство:

2k >= m+k+1.

Например, если m=4, то из этого неравенства находим, k=3 ( так как 23>=4+3+1).

Практически можно получить следующие значения:

 

Количество информационных

разрядов  m

Количество контрольных

разрядов k

1 2
2 — 4 3
5 – 11 4
12 — 26 5
27 — 57 6

 

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

7                6               5              4=22            3                2=21            1=20

 

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

Таблица 16.

Номер строки k3 k2 k1
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

 

Из таблицы исключаются строки, в которых присутствует только одна единица – строки 1, 2, 4.

Оставшиеся строки позволяют определить контролируемые позиции для каждого контрольного разряда. Номера этих позиций равны  номерам строк, в которых в соответствующем столбце стоит единица ( это строки 3, 5, 6 и 7).

В результате:

k1 контролирует четность 3, 5 и 7-го разрядов кода;

k2 контролирует четность 3, 6 и 7-го разрядов кода;

k3 контролирует четность 5, 6 и 7-го разрядов кода.

Выражения для определения контрольных разрядов имеют вид:

k1 = а3а5а7;

k2 = а3а6а7;

k3 = а5а6а7;

  1. В качестве опознавателя используется k-разрядное слово (r3 r2 r1). Его

Разряды определяются по формулам:

r1= k1а3а5а7;

r2= k2а3а6а7;

r3= k3а5а6а7.

Пример. Закодировать по методу Хэмминга число 13. В полученный код ввести одиночную ошибку и с помощью опознавателя определить номер искаженного разряда.

Решение.

  1. Число 13 переводится в двоичную систему счисления: 1310 = 11012

Число двоичных информационных разрядов m=4. Количество контрольных

разрядов k=3 ( было определено ранее).

  1. Для получения полной структуры кода, значения информационных

      разрядов подставляются в соответствующие позиции. Общая структура кода

имеет вид:     1      1       0        k3         1         k2           k1

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

k1 = а3а5а7=101=0;

k2 = а3а6а7=111=1;

k3 = а5а6а7=011=0.

Значения информационных и контрольных разрядов подставляются в

структуру кода.

Калькулятор кодов онлайн.

В результате получается искомый код Хемминга.

 

7                6               5              4=22            3                2=21            1=20

  1. Предполагаем, что в результате сбоя при передаче исказился третий

pазряд кода и его единичное значение изменилось на противоположное

(нулевое). В результате получен код: 1  1  0  0  0  1  0.

Исходя из нового ошибочного значения кода,  вычисляется значение

опознавателя:

r1= k1а3а5а7=00 01=1;

r2= k2а3а6а7=10 11=1;

r3= k3а5а6а=00 11=0.

Опознаватель r3 r2 r1=0112=310, то есть ошибка произошла в третьем разряде.

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

1  1   0   0   1   1    0.

 

По методу Хемминга могут быть построены коды разной длины. При этом, чем больше длина кода, тем меньше относительная избыточность. Например, для контроля числа, имеющего 48 двоичных разрядов, потребу­ется только шесть дополнительных (избыточных) разрядов. Коды Хэмминга используют в основном для контроля передачи информации по каналам связи, что имеет место в вычислительных системах с телеобработкой дан­ных или в системах коллективного пользования.

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *