Оценка качества кода Хемминга для коррекции ошибок

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

 

В процессе хранения информации запоминающие элементы (конденсаторы) динамического ОЗУ подвергаются деструктивному воздействию. Например, a излучению окружающего материала (несколько сантиметров) или космического излучения. В результате бомбардировке частицами высоких энергий микроконденсатор может разрядиться раньше времени и при очередном цикле регенерации с него будет считано не то значение бита, которое было записано. Для устранения этого недостатка динамического ОЗУ применяют код с исправлением ошибок. Каждый сохраняемый байт устройство регенерации записывает в ОЗУ с избыточными битами в коде Хемминга, а при считывании информации исправляет обнаруженную ошибку.

Код Хемминга – один из наиболее распространенных блочных кодов для исправления ошибок. В блочном коде, в отличии от рекурентного кода, рассмотренного выше, информация передаются блоками по k бит. Для обнаружения и исправления ошибок вместе с информационными кодер формирует и передает дополнительные проверочные биты. При помощи этого кода можно обнаружить и исправить в декодере (Рис. 2) все одиночные ошибки в блоке из k информационных бит при помощи r проверочных бит. Поэтому разрядность этого кода с коррекцией ошибок

n=k+r (1)

равна сумме числа k информационных бит и r – проверочных бит. Избыточностью кода для двоичных алфавитов,

R_и = , (2)

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

R= 1-R_и (3)

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

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

, (4)

которое обеспечивает определение положения одного из n искаженных бит и обозначение ситуации отсутствия ошибок (+1). Для k=8 отношение (4) выполняется при r=4. Поэтому, с учетом (1), для исправления одной ошибки возникшей при передаче или хранении одного байта данных необходимо сформировать четыре проверочных бита. Тогда длина кода n=12.

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

R_и=

избыточность в два раза меньшую и

R= ,

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

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

Q_0,8= , q=1-p

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

Q_h=Q_0,12+Q_1,12=

=q¹¹(q+12p)= (учитывая, что p=1-q)

=q11(q+12-12q)=

= q¹¹(12-11q)

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

D=Q_h-Q_0,8= q¹¹(12-11q)-q⁸

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

D=

Рассмотрим случай D=0, тогда уравнение

q¹¹(12-11q)-q⁸=0 (5)

имеет три корня:

q₁=0

q₂=1 и

0<q₃<1

Пусть q=0.3, тогда D_0.3= -5.02×10^-5

q=0.7, тогда D0.7=0.027

Так как D_0.3<0 и D0.7>0, то 0.3<q₃<0.7 третий корень уравнение (5) q₃ может быть найден известными методами. При всех значения вероятности безошибочного приема q£q₃ не больших значения этого корня не приносят эффекта при использовании кода Хемминга для исправления одной ошибки.

Практическая часть

Задано.

1. Рассматривается симметричный двоичный канал передачи, в котором вероятность ошибки при передаче одного бита равна р. Для повышения надежности передачи кодер системы передачи (смю.рис. выше) передает каждый бит трижды, а декодер приемника определяет значение принятого бита, используя схему голосования «не менее 2 из 3».

2. Вероятность ошибки при передаче одного бита равна р=0,200+0,0i, где i Ваш порядковый номер в классном журнале: 01, 02, …26,27.

 

 

Определить.

1. Математическое ожидание m_x и дисперсию D_x числа правильно принятых бит в канале без коррекции ошибок, если вероятность ошибки при передаче бита равна р: при передаче одного, трех и 10 бит.

2. Вероятность Q_m получения безошибочного значения переданного бита, в канале с указанной выше коррекцией ошибок, если вероятность ошибки при передаче бита равна р. Для этого определить значение Qm=Q_0,3+Q_1,3, как сумму вероятностей исходов при троекратной передачи бита, в которых не произошло ни одной ошибки (Q_0,3) и только одна ошибка (Q_1,3).

3. Математическое ожидание m_x и дисперсию D_x числа верно принятых бит в канале с коррекцией ошибок при передаче одного, трех и 10 бит. Канал с коррекцией ошибок это канал, который включает в себя кодер и декодер вместе с передатчиком и приемником. Поэтому можно считать, что через него передается поток одиночных бит.

4. Вероятности Q_m приема безошибочного значения переданного бита, в канале с указанной выше коррекцией ошибок, если вероятности ошибки при передаче бита равны р₁=p, p₂=p+0,1, p₃=p+0,2, p₄=0,5, p₅=p+0,4, p₆=p+0,5, p₇=p+0,7.

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

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

Приложения

Последовательность независимых испытаний

Схема повторных независимых опытов является одной из важнейших схем исследования в теории вероятностей. Опытом будем называть целенаправленное действие, в результате которого может произойти или не произойти некоторое событие А. Далее будем рассматривать простейшие опыты – в результате которых может произойти или не произойти только одно событие А. Событие произошедшее в результате опыта будем называть исходом опыта. Если в результате опыта произошло событие А, то этот исход будет обозначаться этой буквой. Если в результате опыта событие А не произошло, то этот исход будем обозначать Ã букой А со знаком ~ (тильда) над ней. Тогда обозначения исходов опыта интерпретируем следующим образом:

· А – событие А произошло (читаем –А),

· Ã - событие А не произошло (читаем – не А).

В соответствии с определением, в результате опыта обязательно произойдет событие А и исход события будет обозначаться А, либо оно не произойдет, тогда исход опыта будет обозначаться Ã.

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

Если опыты, в которых может произойти событие А производить несколько раз, то исходы этих опытов можно описывать в виде множества возможных исходов каждого опыта. Например, пусть проводиться два опыта, в каждом которых может произойти или не произойти событие А. Тогда все возможные исходы двух опытов можно описать следующим множеством их исходов:

ÃÃ – исход опытов, в которых событие А не произошло ни в первом, ни во втором опыте;

ÃА – исход опытов, в которых событие А не произошло в первом и произошло во втором;

АÃ – исход опытов, в котором событие А произошло в первом и не произошло во втором опыте;

АА – исход опытов, в котором событие А произошло в первом и втором опыте.

Если производиться несколько опытов, то это действие будем называть повторными испытаниями из нескольких опытов. Если производятся испытания из n опытов, то легко показать, что число возможных исходов этих опытов равно 2ⁿ.

Пусть вероятность появления события А в каждом из независимых опытов одинакова и равна р. Тогда вероятность не появления события А в каждом из независимых опытов q=1-p. Так как эти вероятности (p и q) независимы, то вероятности каждого из 2ⁿ исходов могут быть определены как произведения вероятностей соответствующих событий:

ÃÃ ® qq=q² (1)

ÃА ® qp

АÃ ® pq

АА ® pp=p²

Четыре исхода двух независимых опытов (1) образуют полную группу событий, так как их вероятности в сумме равны единице:

Р _ÃÃ+Р _ÃА+Р _АÃ+Р _АА=q²+2pq+p²=(p+q)²=(p+1-p)²=1 (2)

Формула Бернулли. Если производиться n независимых опытов в одинаковых условиях, причем в каждом из них с вероятностью р может появляется событие А, то вероятность Р_m,n того, что событие А произойдет в этих n опытах ровно m (m£n) раз, определяется выражением

Р_m,n= , где q=1-p и . (3)

Перечисление вероятностей (1) и выражение (3) для каждого из 2ⁿ возможных исходов n опытов определяют распределение вероятностей для исходов независимых испытаний.

Законом распределения вероятностей называется соответствие между исходами испытаний и вероятностями этих исходов, полученное в результате испытаний или логических рассуждений. Распределение определяемое (3) называют биномиальным распределением вереятностей. Закон распределения вероятностей может быть представлен рядом распределения – перечислением всех возможных исходов и соответствующих им вероятностей, так как это показано в таблице 1.

Таблица 1

Исходы x	ÃÃ	ÃA	AÃ	AA
Сл. Величина xi
Вероятность	q2	qp	pq	p2

Ряд распределения графически изображают в виде точек на плоскости (событие x,р_x) в системе координат [{полное множество событий},R]. Графическое изображение (график) ряда распределения вероятностей исходов в двух опытах изображен на рисунке 1. В этих опытах вероятность появления события А для p=0,6.

 

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

 

 

Случайной величиной называется величина, которая в результате испытаний может принимать то или иное заранее неизвестное числовое значение. Например, в рассматриваемом испытании из двух опытов, случайной величиной можно считать число появления события А в исходе испытания. Значения этой случайной величины x_iÎX для каждого исхода приведены во второй строке таблицы 1 и на рисунке 1. На рисунке 2 показана обобщенная схема сопоставления событий случайным величинам и случайных величин вероятностям – распределение вероятностей.

Функцией распределения случайной величины Х называется функция F(x), определяющая вероятность того, что случайная величина Х примет значение меньшее чем х:

F(x)=P(X<x).

Тогда на множестве всех исходов и множестве вещественных чисел R можно определить функцию распределения случайной величины так:

F(x)= (4)

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

Таблица 2

x
F(x)=P(X<x)		q2	q2+2pq	q2+2pq+p2=1

F(0)=P(X<0)=0, так как не существует исходов, в которых число появлений события А меньше нуля. F(1)=P(X<1)=q², так как вероятность исхода в котором событие А не появляется ни в первом ни во втором опыте равна q². F(2)=P(X<2)=P(X<1)+P(X<2)=q²+qp+pq=q²+2pq, так как вероятность того, что в двух опытах событие А появится меньше двух раз равна сумме вероятности не появления события А в обоих опытах и вероятности появления события А только один раз. F(3)=P(X<3)=q2+2pq+p2=1, так как в двух опытах событие А обязательно появиться 0,1 или 2 раза (появиться меньше трех раз). Функция распределения вероятностей непрерывна слева, поэтому ее значения обозначены стрелками, направленными влево.