Электронные промышленные устройства. Кузнецов Б.Ф. - 41 стр.

UptoLike

ВУЗ: 

АГТА | Ангарск

Составители: 

Рубрика: 

41
где
p
- вероятность искажения одного символа;
C
t
n
=
n !
t !(n Ў t )!
.
Так как на практике
p ї 1
, то наиболее вероятными являются ошибки низшей кратности. Их
и следует обнаруживать и исправлять в первую очередь.
Простейшим из помехозащищеных кодов является код с проверкой на четность
(d = 2)
, ко-
торый используется при вводе и хранении информации в ЭВМ. В данном случае к кодовой комби-
нации, состоящей из и информационных разрядов
a
1
; a
2
; :::;a
n
, добавляется один дополнитель-
ный (проверочный) разряд
a
0
так, что кодовая комбинация принимает вид:
A
0
= (a
0
a
1
:: :a
n
)
.
Значение проверочного разряда
a
0
вычисляют сложением по модулю 2 значений всех ин-
формационных разрядов:
a
0
= a
1
© a
2
© : : : © a
n
(1.74)
Иначе говоря,
, если общее количество единиц в информационных разрядах кодовой
комбинации является четным числом, или
a
0
= 1
, если это число нечетно. Но тогда при отсутствии
ошибки кодовая комбинация (1.73) всегда содержит четное число единиц и, следовательно, сумма
r = a
0
© a
1
© a
2
© : : : © a
n
(1.75)
должна принимать нулевое значение(
r = 0
). Если в результате проверки установлено, что кон-
трольная сумма (1.75) принимает значение
r = 1
, то это указывает на наличие одиночной ошибки
(или нечетного числа ошибок) в принятой кодовой комбинации. Недостатком данного кода являет-
ся отсутствие возможности автоматической коррекции ошибок.
1.6.7. Код Хемминга*
Примером корректирующего кода, позволяющего обнаружить и исправить одиночную
ошибку(
d = 3
), является код Хемминга, идея построения которого заключается в следующем. До-
пустим,что кодовая комбинация содержит и информационных и
k
проверочных разрядов, причем
значение каждого проверочного разряда определяется суммированием по модулю 2определенного
числа информационных разрядов. После, приема кодовой комбинации производят
k
проверок, за-
ключающихся в вычислении контрольных сумм
r
1
; r
2
; :::;r
k
.Для определенных наборов значе-
ний из всех
(n + k)
разрядов. Если записать результаты данных проверок справа налево, то полу-
чим
k
-разрядное контрольное число
r = (r
k
r
kЎ 1
:: : r
1
)
, которое и указывает номер искаженного
разряда в двоичной системе счисления. Отсутствию ошибки в кодовой комбинации соответствует
контрольное число, составленное только из нулей.
Это число должно описывать
(n + k + 1)
различных событий, включая отсутствие ошибки
или искажение одного из
(n + k)
разрядов. Так как в
k
двоичных разрядах можно записать лишь
2
k
различных контрольных чисел, то обязательным является выполнение условия:
2
k
ё n + k + 1
, (1.76)
откуда можно найти требуемое значение
k
для заданного числа
n
. Некоторые значения
n
и
k
сведе-
ны в таблице 1.4, где указывается относительная избыточность кода
R = k/ (n + k)
, т. е. отношение
числа проверочных разрядов к общей длине кодовой
комбинации.
Результаты проверок
r
1
; r
2
; :::;r
k
в коде Хем-
минга вычисляются в соответствии с проверочными
уравнениями:
r
1
= a
1
© a
3
© a
5
© a
7
: : : ;
r
2
= a
2
© a
3
© a
6
© a
7
: : : ;
r
3
= a
4
© a
5
© a
6
© a
7
: : : ;
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Первое уравнение включает в себя те разряды
кодовой комбинации, в номерах которых в двоичной
Таблица 1.4
n
k
n + k
R = k/ (n + k)
1
2
3
0.67
2
3
5
0.6
3
3
6
0.5
4
3
7
0.43
5
4
9
0.44
6
4
10
0.4
7
4
11
0.36 
                                                                                                   41


где p- вероятность искажения одного символа; Cnt =             n!
                                                         t !( n Ў t ) ! .
      Так как на практике p ї 1, то наиболее вероятными являются ошибки низшей кратности. Их
и следует обнаруживать и исправлять в первую очередь.
      Простейшим из помехозащищеных кодов является код с проверкой на четность (d = 2), ко-
торый используется при вводе и хранении информации в ЭВМ. В данном случае к кодовой комби-
нации, состоящей из и информационных разрядов a1; a2; : : : ; an , добавляется один дополнитель-
ный (проверочный) разряд a0так, что кодовая комбинация принимает вид:
                                         A 0 = (a0 a1 : : : an ).
       Значение проверочного разряда a0 вычисляют сложением по модулю 2 значений всех ин-
формационных разрядов:
                                          a0 = a1 © a2 © : : : © an                       (1.74)
       Иначе говоря, 0
                    a  = 0, если общее количество единиц в информационных разрядах кодовой
комбинации является четным числом, или a0 = 1, если это число нечетно. Но тогда при отсутствии
ошибки кодовая комбинация (1.73) всегда содержит четное число единиц и, следовательно, сумма
                                           r = a0 © a1 © a2 © : : : © an                  (1.75)
должна принимать нулевое значение( r = 0). Если в результате проверки установлено, что кон-
трольная сумма (1.75) принимает значение r = 1, то это указывает на наличие одиночной ошибки
(или нечетного числа ошибок) в принятой кодовой комбинации. Недостатком данного кода являет-
ся отсутствие возможности автоматической коррекции ошибок.


                                      1.6.7. Код Хемминга*

       Примером корректирующего кода, позволяющего обнаружить и исправить одиночную
ошибку(d = 3), является код Хемминга, идея построения которого заключается в следующем. До-
пустим,что кодовая комбинация содержит и информационных и k проверочных разрядов, причем
значение каждого проверочного разряда определяется суммированием по модулю 2определенного
числа информационных разрядов. После, приема кодовой комбинации производят k проверок, за-
ключающихся в вычислении контрольных сумм r 1; r 2; : : : ; r k .Для определенных наборов значе-
ний из всех (n + k)разрядов. Если записать результаты данных проверок справа налево, то полу-
чим k -разрядное контрольное число r = (r k r kЎ 1 : : : r 1 ), которое и указывает номер искаженного
разряда в двоичной системе счисления. Отсутствию ошибки в кодовой комбинации соответствует
контрольное число, составленное только из нулей.
       Это число должно описывать (n + k + 1) различных событий, включая отсутствие ошибки
или искажение одного из (n + k)разрядов. Так как в k двоичных разрядах можно записать лишь 2k
различных контрольных чисел, то обязательным является выполнение условия:
                                              2k ё n + k + 1,                                   (1.76)
откуда можно найти требуемое значение k для заданного числа n . Некоторые значения n и k сведе-
ны в таблице 1.4, где указывается относительная избыточность кода R = k/ (n + k), т. е. отношение
                                           числа проверочных разрядов к общей длине кодовой
  Таблица 1.4
                                           комбинации.
   n     k     n+ k      R = k/ (n + k)          Результаты проверок r 1; r 2; : : : ; r k в коде Хем-
   1      2       3           0.67         минга вычисляются в соответствии с проверочными
   2      3       5            0.6         уравнениями:
                                                      r 1 = a1 © a3 © a5 © a7 : : : ;
   3      3       6            0.5                    r 2 = a2 © a3 © a6 © a7 : : : ;
   4      3       7           0.43                    r 3 = a4 © a5 © a6 © a7 : : : ;
   5      4       9           0.44                    ::::::::::::::::::::::::::::::
                                                 Первое уравнение включает в себя те разряды
   6      4      10            0.4         кодовой комбинации, в номерах которых в двоичной
   7      4      11           0.36

Страницы