Топоркова О.М. Информатика - файл n1.doc

приобрести
Топоркова О.М. Информатика
скачать (1710.5 kb.)
Доступные файлы (1):
n1.doc1711kb.26.08.2012 21:38скачать
Победи орков

Доступно в Google Play

n1.doc

1   ...   5   6   7   8   9   10   11   12   ...   30

4.4. Помехозащитное кодирование



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

4.4.1. Искажение кодовых комбинаций


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

При передаче по каналу связи на передаваемый код накладывается ошибка, которая формально представляется кодовой комбинацией с числом разрядов, равным числу разрядов передаваемого кода, содержащей 1 в искажаемых разрядах. Так, если a1a2…ak – передаваемая кодовая комбинация, то b1b2…bkошибка (ai = {0,1},, bi = {0,1}, i=1,k).

С ошибкой связано понятие ее кратности q – это число искажаемых ошибкой разрядов, т.е. число единиц в ее коде.

Искажение рассматривается как сложение по модулю 2 исходной кодовой комбинации и ошибки:

a1a2…ak b1b2…bk = c1c2…ck ,

где c1c2…ck – искаженная кодовая комбинация.

Пусть имеется таблица кодов из табл. 4.2 и кратность ошибки равна 1, т.е. соответствующие ошибке кодовые комбинации – элементы множества {01, 10}. Пусть передается кодовая комбинация 10 (код символа c). Тогда возможное искажение представлено в табл. 4.11.

Таблица 4.11

Передаваемая

кодовая комбинация

Ошибка

Принимаемая

кодовая комбинация

Результат декодирования

10

01

11

d

10

10

00

a


Таким образом, в результате ошибки принимающая сторона вместо символа c примет символ d или a и ошибка даже не будет обнаружена.

4.4.2. Кодовое расстояние и корректирующая способность кода


Под корректирующей способностью кода понимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности q. Корректирующая способность кода связана с его кодовым расстоянием.

Расстоянием dij между кодами (кодовыми комбинациями) i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

К

(4.5)
одовым расстоянием
d для кода, содержащего m кодовых комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций, т.е.

где ij, i=1,m; j=1,m.

Для кода из табл. 4.2:

dab = 1; dad = 2; dbd = 1; dac = 1; dbc = 2; dcd = 1.

Тогда d = min{1, 2, 1, 1, 2, 1} = 1. Это означает, что всякая ошибка кратности 1 (и более) переводит исходную кодовую комбинацию в другую кодовую комбинацию, которая также принадлежит коду.

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

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

Вернемся к таблице кодов из табл. 4.2, введем дополнительный разряд и сформируем его значение. Результат – в табл. 4.12.

Таблица 4.12

Исходные

символы

Информационные

разряды кода

Проверочный

разряд кода

Результирующий

код

a

00

0

000

b

01

1

011

c

10

1

101

d

11

0

110


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

Определим кодовое расстояние полученного кода:

dab = 2; dad = 2; dbd = 2; dac = 2; dbc = 2; dcd = 2.

Тогда d = min{2, 2, 2, 2, 2, 2} = 2.

Пусть передается кодовая комбинация, соответствующая символу c, – 101. Пусть на нее накладывается ошибка кратности 1. Возможные результаты искажения приведены в табл. 4.13.

Таблица 4.13

Передаваемая

кодовая комбинация

Ошибка

Принимаемая

кодовая комбинация

Результат

декодирования

101

001

100

Невозможно декодировать

101

010

111

То же

101

100

001

“-“


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

Последний пример дает возможность ввести понятия разрешенных и запрещенных кодовых комбинаций.

Разрешенными кодовыми комбинациями называются те, которые присутствуют в исходной кодовой таблице (см. результирующий код в табл. 4.12). Их количество равно числу исходных символов (m). Запрещенные кодовые комбинации – это те, которые отсутствуют в исходной кодовой таблице. Их количество определяется по формуле: 2r m, где r – общее число двоичных разрядов (информационные плюс проверочные) в коде.

Сформируем все разрешенные и запрещенные кодовые комбинации для кода из табл. 4.12, при этом используем схему формирования кода Грея (рис. 4.3). Обозначения строк – исходные коды из табл. 4.2, обозначения столбцов – значения проверочных разрядов.




0

1

00

a




01




b

11

d




10




c


Рис. 4.3. Схема формирования помехозащитного кода из примера

Здесь пустые ячейки означают запрещенные кодовые комбинации. Как видно из рис. 4.3, отстояние кодовых комбинаций для исходных символов a, b, c, d равно двум разрядам:

Поэтому при наличии ошибки кратности 1 кодовая комбинация переходит в соседнюю запрещенную.

До введения проверочного разряда формирование кода из табл. 4.2 можно было представить схемой, показанной на рис. 4.4.




0

1

0

a

b

1

c

d


Рис. 4.4. Схема формирования кода из примера 4.1
Поскольку символы расположены плотно в схеме, всякое искажение кода приводило к попаданию в другую ячейку с кодом.

Очевидно, коды, построенные по схеме рис. 4.3, не позволяют обнаружить ошибку кратности 2: в самом деле, при этом кодовая комбинация переходит в другую разрешенную кодовую комбинацию.

Существует связь между кодовым расстоянием d и минимальной кратностью ошибки q, которую код может обнаруживать:

dq + 1. (4.6)

Пример 4.9. На базе кода из табл. 4.12 построить код, обнаруживающий ошибки кратности 2.

Воспользуемся схемой формирования кода Грея с некоторыми модификациями.

Поскольку код для обнаружения ошибки кратностью 1, построен, используем его для обозначения строк схемы, причем с каждой строкой свяжем символ, который соответствует данной кодовой комбинации: так с первой строкой свяжем символ a, со второй – b и т.д. Очевидно, кодовые комбинации в обозначении строк схемы различаются двумя разрядами.

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

С учетом сделанных замечаний схема имеет 4 столбца и 4 строки и представлена на рис. 4.5.




00

01

11

10

000

a










011




b







110







d




101










c



Рис. 4.5. Схема формирования кода Грея для примера 4.9
Таким образом, построен следующий код:

00000  a, 01101  b, 11011  d, 10110  c.

Определим кодовое расстояние d построенного кода:

dab = 3; dad = 4; dbd = 3; dac = 3; dbc = 4; dcd = 3.

Тогда dmin = {3, 4, 3, 3, 4, 3} = 3.

Проверим, обнаруживает ли построенный код ошибку кратности 2. Для этого зададимся произвольной кодовой комбинацией, например, 01101 (символ b). Результат проверок приведен в табл. 4.14.

Таблица 4.14

Передаваемая

кодовая комбинация

Ошибка

Принимаемая

кодовая комбинация

Результат

Декодирования

01101

00011

01110

Невозможно декодировать

01101

00101

01000

То же

01101

00110

01011

“-“

01101

01001

00100

“-“

01101

01010

00111

“-“

01101

01100

00001

“-“

01101

10001

11100

“-“

01101

10010

11111

“-“

Продолжение табл. 4.14

01101

10100

11001

“-“

01101

11000

10101

“-“


Таким образом, задача решена.

В заключение отметим, что существует несколько возможных кодов, решающих задачу из примера 4.9. В самом деле, возможны несколько схем формирования кода, одна из которых показана на рис. 4.6.




00

01

11

10

000




a







011

b










110







d




101










c


Рис. 4.6. Схема формирования кода для примера 4.9 (один из возможных вариантов)

4.4.3. Коды, исправляющие ошибки


Особое значение имеют помехозащитные коды, которые могут исправлять ошибки определенной кратности. Соотношение между максимальной кратностью исправляемой ошибки q и кодовым расстоянием d определяется по формуле (4.7):

d 2q + 1. (4.7)

В основу исправления ошибок положена следующая идея: определяется множество кодовых комбинаций, включающее все разрешенные и те запрещенные, которые получены при искажении ошибкой кратности не более q. Это множество разбивается на m подмножеств, где m – число исходных кодируемых символов. В каждое подмножество входят: разрешенная кодовая комбинация и ближайшие к ней запрещенные, которые отстоят от разрешенной на расстояние не больше q. Например, при построении помехозащитного кода для двух символов, способного исправлять ошибки кратности не больше q, подобное разбиение может выглядеть так, как показано на рис. 4.7.




q q

….. 1 …..


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

Тогда при декодировании определяется, в какое подмножество входит принятая кодовая комбинация. Если она является разрешенной, то сразу декодируется; если запрещенная, то исправляется на разрешенную, с которой находится в одном подмножестве, а затем декодируется.

Пример 4.10. Построить помехозащитный код, исправляющий ошибку кратности 1, для передачи двух символов: a и b.

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

a 0,

b 1.

В силу (4.7) и поскольку по заданию q = 1, имеем d = 3, таким образом, для исправления ошибки кратности 1 кодовое расстояние должно быть равно по меньшей мере 3.

Поскольку в первичном коде обеспечено расстояние между кодовыми комбинациями, равное 1, для выполнения условия d = 3 необходимо, чтобы проверочные разряды обеспечивали расстояние между кодовыми комбинациями, по меньшей мере, равным 2.

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

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

символ разряд разряды код

a 0 00 000

b 1 11 111

Очевидно, кодовое расстояние равно 3, а построенные кодовые комбинации являются разрешенными.

Определим общее число всевозможных комбинаций, если число разрядов кода равно 3:

000 - разрешенная кодовая комбинация,

001

010

0
- запрещенные кодовые комбинации,
11

100

101

110

111 - разрешенная кодовая комбинация.
Определим подмножества кодовых комбинаций, которые отстояли бы от каждой разрешенной на минимальное расстояние, равное 1:

для 000 для 111

001 011

010 101 (4.8)

  1. 110.

Пусть передается кодовая комбинация 000 (символ a) и на нее накладывается ошибка кратности 1. В табл. 4.15 показаны полученные кодовые комбинации и их декодирование.

Таблица 4.15

Передаваемая

кодовая комбинация

Ошибка

Принимаемая

кодовая комбинация

Результат

исправления (см. (4.8))

Результат декодирования

000

100

100

000

a

000

010

010

000

a

000

001

001

000

a



Таким образом, построенный код позволяет исправлять ошибки кратности 1.

Пример 4.11. Построить помехозащитный код, исправляющий ошибку кратности 1, для передачи символов: a, b и c.

Построим первичный код: a – 00; b01; c10.

Для решения поставленной задачи необходимо обеспечить d = 3 (см. пример 4.10).

Воспользуемся схемой формирования кода Грея из примера 4.9:




00

01

11

000

a







011




b




101







c


Таким образом, получены коды:

a  00000, b  01101, c 10111.

Полученное кодовое расстояние d = min {dab, dac, dbc} = min {3, 4, 3} = 3 обеспечивает исправление ошибки кратности q = 1.

Рассмотрим, как исправляются ошибки в данном случае. Все множество кодовых комбинаций пятиразрядного двоичного кода равно 25 = 32. Из них три кодовые комбинации – разрешенные, остальные – запрещенные. Разобьем кодовые комбинации на три подмножества, в каждое из которых будут входить: одна разрешенная и те запрещенные, которые отстоят от разрешенной на расстояние в 1. Имеем:

для 00000 для 01101 для 10111

00001 01100 10110

00010 01111 10101

00100 01001 10011 (4.9)

01000 00101 11111

10000 11101 00111

Очевидно, общее число кодовых комбинаций, включенных в построенные подмножества, равно 24. Оставшиеся 8 кодовых комбинаций являются следствием ошибки кратности больше 1 и в сформированные подмножества не включены.

Проверим, как выполняется исправление ошибки кратности 1. Пусть передается кодовая комбинация 01101 (символ b) и на нее накладывается ошибка кратности 1. В табл. 4.16 показаны полученные кодовые комбинации и их декодирование.

Таблица 4.16

Передаваемая

кодовая комбинация

Ошибка

Принимаемая

кодовая комбинация

Результат

исправления (см. (4.9))

Результат декодирования

01101

10000

11101

01101

b

01101

01000

00101

01101

b

01101

00100

01001

01101

b

01101

00010

01111

01101

b

01101

00001

01100

01101

b


Пусть на ту же кодовую комбинацию накладывается ошибка кратности 2 (табл. 4.17). Результирующие кодовые комбинации либо невозможно декодировать, либо декодирование неверно.

Таблица 4.17

Передаваемая

кодовая комбинация

Ошибка

Принимаемая

кодовая комбинация

Результат декодирования

01101

10001

11100

Невозможно декодировать

01101

01001

00100

То же

01101

00101

01000

a

01101

00011

01110

Невозможно декодировать

01101

10010

11111

с

01101

01010

00111

То же

01101

00110

01011

Невозможно декодировать

01101

10100

11001

То же

01101

01100

00001

а

01101

11000

10101

с


В заключение отметим, что для обнаружения ошибки кратности q1 и исправления ошибки кратности q2 (q1q2) минимальное кодовое расстояние должно удовлетворять следующему соотношению:

d  q1 + q2 + 1.
1   ...   5   6   7   8   9   10   11   12   ...   30


4.4. Помехозащитное кодирование
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации