Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика 2015

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

Они хочут свою образованность показать, и говорят о чём-то непонятном.

А.П.Чехов

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

Автоматическое обнаружение и исправление ошибок сопровождается введением избыточности в передаваемые или хранимые данные. Для этих целей разработаны специальные коды, в которые помимо информационных битов Ь,Ь,...Ь„ дополнительно вводят контрольные (проверочные) биты

к1к,...кт- Контрольные биты позволяют проверять целостность (неискажён-

ность) информационных битов машинного слова, а наиболее сложные коды могут нс только обнаружить, но и исправить неверно принятые биты.

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

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

Проверочный бит к для п-битного двоичного слова Ь,Ь.....Ь. вычисляется по формуле:

В результате такого преобразования формируется (п+1) - битное слово blb2...b„k , число единиц в котором будет четное.

Рассмотрим пример.

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

Идею обнаружения и определения неверно принятого бита можно проиллюстрировать с помощью кода Хэмминга. Для иллюстрации принципа кодирования можно воспользоваться диаграммами Вена [21]. Пусть

передаётся сообщение 1010. Окружности А, В и С дают семь сегментов. В четыре внутренних сегмента помещаются информационные биты числа 1010 (см. рис. а). Оставшиеся три сегмента дополняются контрольными битами (рис. Ь).

Правило формирование контрольных битов такое: в каждой окружности должно быть четное число единиц. В данном случае в каждой окружности получилось но две единицы. Пусть в процессе передачи информации один информационный бит будет искажён (рис. с). На приемной стороне осуществляется анализ принятой информации. Легко заметить, что в окружности С число единиц осталось четным, а окружностях А и В число единиц стало нечетным. Это говорит о гом, что искаженный бит находится в сегменте, который принадлежит окружностям А и В, но не принадлежит окружности С (рис. d).

Рассмотрим пример нахождения искажённого бита с помощью кода Хэмминга. Места расположения информационных битов (ИБ) и контрольных битов (КБ) в передаваемых данных указаны в следующей таблице. В верхней строке таблицы записан порядковый номер каждого бита в машинном слове.

раз.

12

11

10

9

8

7

6

5

4

3

2

1

ИБ

К

ь7

К

ь5

ь4

ьз

ь2

bi

КБ

со

К

к2

К

Форма записи машинного слова, приведенная в предыдущей таблице, выбрана такой с целью повышения наглядности (из методических соображений). Фактически данные представляют единым двенадцатибитным машинным словом: Ь8Ь7Ь6Ь5к8Ь4Ь3Ь2к4Ьгк2кг-

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

Разряд

12

И

10

9

8

7

6

5

4

3

2

1

Слово

ь8

ь7

ь6

ь5

со

ь4

ьз

ь2

К

Ьт

К

ИБ

1

0

0

0

1

1

0

1

КБ

0

1

0

0

Вычислим значения контрольных битов на приеме. Будем обозначать проверочные биты на приеме со штрихом (чтобы отличить их от контрольных битов, сформированных на передающей стороне). Расчет производится по формулам [21]:

Используя предыдущие формулы и исходные данные, получим значения контрольных битов на приёме:

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

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

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

Используя результаты расчётов и исходные данные, можно определить четыре бита синдрома:

Перевод синдрома S = 10102 из двоичной системы счисления в десятичную СС даёт значение S = 10]0. Десятичное число 10 говорит о том, что десятый разряд принятых данных б) искажён, и этот бит нужно исправить (проинвертировать). Таким образом, после корректировки принятые данные будут иметь вид, показанный в следующей таблице. Напомним, что счет разрядов ведётся справа налево.

Разряд

12

И

10

9

8

7

6

5

4

3

2

1

Слово

СО

Ьу

К

ь5

00

ь4

Ьз

ь2

К

Ь,

К

ИБ

1

0

1

0

1

1

0

1

КБ

0

1

0

0

Устранить две ошибки (и более) в принятых данных позволяют циклические коды Боуза-Чоудхури-Хоквингема (БЧХ).

Циклический код БЧХ v(x) на передающей стороне формируется следующим образом [22]:

где X - фиктивная переменная; и(х) - кодируемая последовательность данных (информационные биты, сообщение); п - число бит в передаваемых данных (суммарное число информационных и контрольных бит); к - число информационных бит в машинном слове; mod - операция вычисления остатка от деления; + - операция конкатенации (соединения, склеивания) информационных и контрольных битов; д(х) - порождающий полином.

В приведённом выше выражении первое слагаемое описывает информационные биты, сдвинутые влево на Хп к разрядов. Второе слагаемое описывает контрольные биты.

Выберем одну из разновидностей БЧХ с кодовой последовательностью длиной п = 15. Данный код формируется с помощью порождающего полинома восьмой степени (г =8):

Число информационных разрядов в таком коде /с = п - г = 15 —8=7. Код позволяет исправить две ошибки (s = 2).

Рассмотрим порядок построения циклического кода БЧХ на передающей стороне.

Дано 7 информационных бит 1011011. Запишем информационные биты в виде полинома:

Порядок построения полинома и(х) иллюстрирует следующая таблица:

Номера

разрядов

7

6

5

4

3

2

1

Слагаемые

X6

X5

X4

X3

X2

X

1

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

Для нахождения первого слагаемого в выражении (1) нужно полином

(2) умножить на X8 (заметим, что число контрольных битов n-k =15-7=8):

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

Для нахождения контрольных битов нужно найти остаток от деления полинома (3) на порождающий полином д(х):

Именно контрольные биты (4) позволяют на приёмной стороне определить, есть ли искажения и при необходимости восстановить неверно принятые биты. Сформированный в соответствии с (1) помехоустойчивый код описывается полиномом:

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

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

В процесс передачи но каналу связи (или записи в намять цифрового устройства) сформированный код БЧХ у( х) может быть искажён и на приём поступит код f(x) ? Декодирование полученных данных /(х) происходит в соответствии со следующим алгоритмом:

  • 1) выполняется деление принятой последовательности /'(х)на порождающий полином д[х):
  • 2) вычисляется вес остатка W (количество единиц в остатке);
  • 3) если W > S, где S - допустимое число ошибок, исправляемых данным кодом, то производится циклический сдвиг влево на один разряд принятой последовательности f (х) и вновь выполняется шаг 1;
  • 4) если W <= S, то производится суммирование полученной последовательности с остатком;
  • 5) производится циклический сдвиг полученной последовательности вправо на количество разрядов, равное числу сдвигов влево, выполненное в

процессе декодирования принятой последовательности.

При описании алгоритма декодирования использован термин «циклический сдвиг». Сдвиг - это изменение позиций битов в машинном слове на одну и ту же величину. Следующий рисунок иллюстрирует порядок перемещения битов при циклических сдвигах влево и вправо.

На рисунке приняты обозначения: LSB - младший значащий разряд; MSB - старший значащий разряд.

Рассмотрим процесс декодирования на примере кода, сформированного ранее.

Предположим, что в данных (6) произошло искажение разрядов 13 и 11. В результате на приём поступило двоичное число 111001101101101.

Запишем его в виде полинома:

Выполним декодирование. Результаты расчетов на каждой итерации поместим в таблицу. Так как данный код позволяет исправлять две ошибки (s = 2), расчёты следует вести до тех нор, пока не будет выполнено условие W < 2.

Иг.

Полиномы

Вес

W

1

Гм

х14 + х13 + х12 + х9 + х8 + х6 + х5 + х3 + х2 +1

С‘(х)

х62

Р'м

х6 + х5 + х3 +1

4

2

f2M

х14 + х1310 + х9 + х +х6 + х43 + Х + 1

С2(х)

х6 + х43 +1

Р2(х)

7 6 4

X +х +х +х

4

3

/3(Х)

х1411 + х10 + х87 + х54 + X2 +Х + 1

С3(х)

X6 + X5 + X

Р3(х)

х65 + х42 +1

5

4

/4(Х)

х12 + Xй + X9 + X8 + X6 + X5 + X3 + X2 + X + 1

С4(Х)

х42 +1

Р4(Х)

х7 + X6 + X5 + X3 + X

5

5

/5(Х)

х13 + х1210 + х9 + х7 + х6 + х43 + х2 + х

С5(х)

х5 + х3 + х +1

Р5(Х)

х2 +1

2

В таблице использованы такие обозначения:

С'(х) - частное от деления f' (х) на порождающий полином д(х) на; - той итерации; р'(х) - остаток от деления /'(х)на порождающий полином д(х) на ! - той итерации.

Па пятой итерации вес остатка достиг значения, при котором следует прекратить дальнейшие расчеты (w = 2). За пять проведенных итераций было выполнено четыре циклических сдвига влево.

Выполненные операции позволяют наглядно понять, почему этот код называю циклическим. При выполнении сдвига влево крайний левый разряд считался соседним с крайним правым разрядом. По этой причине на итерациях 2, 3, 4 последними слагаемыми полиномов /'(х) являются единицы. Эго объясняется тем, что в этих случаях х14 =1 и единица переходит в младший разряд последовательности. На пятой итерации полином /5(х)нс содержит слагаемого, равного 1. Это происходит потому, что на предыдущей итерации х14 = 0.

В соответствии с алгоритмом декодирования теперь следует перейти к шагу 4 и найти сумму величин на последней итерации:

Полученный полином (7) преобразуем в двоичное число:

В соответствии с шагом 5 алгоритма декодированную последовательность (8) нужно циклически сдвинуть вправо на четыре разряда. Этапы сдвига показаны в таблице.

Номера сдвигов

Числа

Щх)

011011011011011

1 сдвиг

101101101101101

2 сдвиг

110110110110110

3 сдвиг

011011011011011

4 сдвиг

101101101101101

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы