bigpo.ru
добавить свой файл
1 2 3
ЛЕКЦИЯ 3

КОДИРОВАНИЕ ИНФОРМАЦИИ


3.1. Простейшие коды

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

Главнейшим показателем кода является значность кода или алфавит выбранных элементарных сигналов (символов), используемых для записи информации в выбранном коде. Если выбирается алфавит из двух элементов (букв), например, 0 и 1, то такой код (алфавит) называют двоичным или бинарным, если число элементарных сигналов (букв) выбирают больше двух, то такой код (алфавит) называют многозначным (например, если количество букв алфавита – десять: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – такой код называют десятичным). Преобразование информации из одного вида (системы обозначений) в другой вид (систему обозначений) называют кодированием.

Например, в двоично-десятичном кодировании, каждая десятичная цифра (сообщение) представляется группой двоичных символов, состоящих из 4-х элементов. Общее число возможных комбинаций двоичного 4-х разрядного числа составляет N = 24 = 16, используется для представления десятичного числа только 10 комбинаций, 6 являются лишними (избыточными), что дает возможность построить большее количество вариантов кода.

При рассмотрении двоичного представления десятичных цифр видно, что использование первых 4-х степеней цифры 2 (20, 21, 22, 23) приводит к одному из возможных кодов 8-4-2-1. Каждый разряд этого кода имеет постоянный вес. Возможны и другие двоично-десятичные коды с другими весами разрядов двоичного числа, например:


7-4-2-1

7-3-2-1

3-3-2-1

6-3-1-1

6-4-2-1

6-3-2-1

6-2-2-1

5-3-1-1

5-4-2-1

5-3-2-1

5-2-2-1

4-3-1-1

4-4-2-1

4-3-2-1

4-2-2-1

5-2-1-1


Эти коды представляют десятичное число от 0 до 9, однако, они не имеют однозначности в изображении десятичных чисел. Например, код
4-3-2-1 дает определение числа 6 в виде: 0111 или 1010.

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

Широкое распространение в вычислительной технике нашли самодополняющие коды, как двоично-десятичные коды со свойством самодополнения до 9. Такие коды обусловлены заменой операции вычитания операцией сложения в ЭВМ, выполняемых в обратных и дополнительных кодах. Наиболее распространенными кодами является код 2-4-2-1 (код Айкена) и код 8-4-2-1 с избытком 3.

Из таблицы видно, что при инвертировании цифр всех четырех разрядов (замены 0 на 1 и наоборот) получается дополнение до 9 для кодируемой десятичной цифры.






Код Айкена

(2-4-2-1)

Код с избытком 3

(8-4-2-1)

0

0000

0011

1

0001

0100

2

0010

0101

3

0011

0110

4

0100

0111

5

1011

1000

6

1100

1001

7

1101

1010

8

1110

1011

9

1111

1100


В двоичных кодах при переходе от изображения одного числа к изображению соседнего (старшего или младшего) возможно изменение символов в нескольких разрядах двоичного числа. Так, при переходе от изображения числа 7 (0111) к изображению числа 8 (1000) одновременно меняются символы во всех четырех разрядах. Это может являться источником ошибок при кодировании непрерывных сигналов в двоичный код.

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

Особенности кода Грея:

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

  2. в коде можно выделить оси симметрии (оси отражения), относительно которых наблюдается идентичность в некоторых разрядах (в первом разряде 00-11-00-11-...; во втором 0000-1111-0000-1111-... и т.д.).




0

0000




8

1100

1

0001




9

1101

2

0011




10

1111

3

0010




11

1110

4

0110




12

1010

5

0111




13

1011

6

0101




14

1001

7

0100




15

1000


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

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

Для перевода простого двоичного кода в код Грея нужно:

  1. под двоичным числом записать такое же число со сдвигом вправо на один разряд (при этом младший разряд сдвигаемого числа теряется);

  2. произвести поразрядное сложение двух чисел по модулю 2 (четности).

Пример: 11010011 перевести в код Грея.

11010011

1101001(1)

10111010 получен код Грея.


Обратный перевод кода Грея в простой двоичный код решается следующим способом:

  1. цифра старшего разряда остается неизменной;

  2. каждая последующая цифра (при движении от старшего разряда к младшему) инвертируется столько раз, сколько единиц ей предшествует в коде Грея.

Пример: 10111010 перевести в простой двоичный код.

11010011.


Литература:

[2] стр. 19. [3] стр. 17.


Контрольные вопросы:

  1. Почему в двоично-десятичном кодировании возможно применить несколько разных способов кодирования?

  2. Для чего применяются самодополняющие коды?

  3. Как построен код с избытком 3?

  4. В чем особенность кода Грея?


^ 3.2. Помехоустойчивые коды

3.2.1. Классификация помехоустойчивых кодов

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

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

Итак, для передачи некоторого количества информации необходима последовательность из k символов. Для придания последовательности корректирующих свойств она удлиняется до n>k символов. Вводимая при этом избыточность определяется коэффициентом избыточности Kизб = k/n.

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

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

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

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





3.2.2. Простейшие коды, обнаруживающие ошибки

Код с удвоением элементов

Каждый символ безызбыточной комбинации дополняется противоположным проверочным, т.е. 1 записывается в виде 10, а 0 - в виде 01. Так, кодовая комбинация 10101 после кодирования превращается в следующую: 10.01.10.01.10.

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

Декодирование сводится к процедурам:

  1. Разделяются информационные и проверочные символы.

  2. Последовательность проверочных символов инвертируется (каждый символ 1 заменяется на 0 и наоборот).

  3. Инвертированная и информационная последовательности суммируются поразрядно по модулю 2.

  4. Анализируется полученная сумма. Наличие в сумме единиц означает ошибки в принятой комбинации.

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


^ Код с четным числом единиц

В этом случае кодирование сводится к добавлению в исходную комбинацию еще одного - проверочного символа. Значение проверочного символа выбирается таким, чтобы сумма по модулю 2 всех символов с учетом проверочного была равна 0, т.е. чтобы в закодированной комбинации было четное число единиц.

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


^ Инверсный код

Кодирование в данном коде заключается в следующем. Если кодируемая комбинация содержит четное количество единиц, она повторяется дважды в неизменном виде, если нечетное - информационная комбинация продолжается информационной инвертированной. Например, комбинация 0011 кодируется так: 0011.0011, а комбинация 0111 - так: 0111.1000.

Декодирование производится следующим образом.

  1. Суммируются единицы в основной части полученной комбинации. Если их количество оказывается четным, то основная комбинация суммируется по модулю 2 о дополнительной, если нечетным - дополнительная часть комбинации инвертируется, а затем суммируется по модулю 2 с основной.

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

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

Избыточность такого кода Kизб = 0,5.


Литература:

[1] стр. 235-241. [2] стр. 257-262. [3] стр. 131-134


Контрольные вопросы:

  1. Дайте определение блочных и непрерывных кодов.

  2. Чем обусловлена помехоустойчивость исправляющих и обнаруживающих ошибки кодов? В чем их различие?

  3. Могут ли исправляющие коды применяться для обнаружения ошибок?

  4. Какие ошибки не обнаруживает код с удвоением элементов?

  5. Какие ошибки не обнаруживает инверсный код?


^ 3.3. Блочные линейные корректирующие коды

3.3.1. Общая характеристика блочных кодов

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

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

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


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

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

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

Для коррекции наиболее вероятных ошибок, т.е. ошибок малой кратности, следует принимать решение, что была передана та разрешенная комбинация, которая отличается от принятой наименьшим числом символов. Различие между комбинациями принято характеризовать расстоянием Хэмминга d, равным числу разрядов, в которых две комбинации имеют различные, т.е. не совпадающие символы. Например, комбинация 0100 отличается от комбинации 1000 в двух разрядах, следовательно, дистанция (расстояние) Хэмминга между этими комбинациями равна двум. Чем больше минимальное расстояние между разрешенными комбинациями кода (кодовое расстояние d0), тем больше корректирующие возможности кода. Так, при кодовом расстоянии d0 = 2 код дает возможность обнаруживать только одиночные ошибки, при d0 = 3 - исправляет все одиночные ошибки или обнаруживает все одиночные и двойные ошибки. В общем случае для исправления ошибок кратности до S включительно кодовое расстояние должно удовлетворять условию d0≥2S+1.

Пример. Множество трехразрядных комбинаций в трехмерном пространстве представляет собой множество вершин куба с длиной ребер, равной единице
(рис. 3.1).

Из рис. 3.1 ясно, что при необходимости исправления всех одиночных ошибок в качестве разрешенных следует выбирать две комбинации, соответствующие противоположным вершинам куба (например, 101 и 010 или 000 и 111). Если необходимо только обнаруживать одиночные ошибки, в качестве разрешенных можно брать комбинации, различающиеся в двух разрядах (например, 001, 010 и 111).

Рассмотрим кратко свойства наиболее широко применяемых кодов.


3.3.2. Групповые коды

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


В линейной алгебре группой называется множество элементов, в котором определена основная операция (обычно обозначается ), причем она должна быть ассоциативной (a(bc)=(ab)c), а для коммутативных групп (групп Абеля) - и коммутативной (ab = ba) и должна обладать обратной операцией. Группы, состоящие из конечного числа элементов, называются конечными. В конечной группе в результате операции, применяемой к любым элементам группы, должны образовываться также элементы этой группы. Последнее свойство называется свойством замкнутости.

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

Сложение и умножение элементов кода по модулю 2 (четности) производится по следующим правилам:

0  0 = 0; 0  1 = 1; 1  1 = 0 (3.1)

0  0 = 0; 0  1 = 1; 1  1 = 1

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

Ознакомимся подробнее с теорией двоичных систематических кодов. Проверочные символы в этом случае находятся путем следующих алгебраических операций. Суммируется по модулю 2 количество единиц в определенных информационных разрядах и добавляется такое значение проверочного символа (1 или 0), чтобы вся сумма по модулю 2 была равна нулю, т.е., чтобы общее количество единиц было четным. Такое равенство называют проверочным. При декодировании проверяется выполнение этих равенств. Невыполнение хотя бы одного из них означает ошибку в принятой комбинации.

Количество информационных символов N0 = 2n – 1 или число разрядов двоичного кода n, общая длина (число разрядов) всей закодированной комбинации m = n + r, где r – число разрядов проверочных (избыточных), что составляет в двоичном коде 2m = N разрешенных кодовых комбинаций. Код обозначается (m, n).

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

Если имеется Е векторов ошибок, то число двоичных неразрешенных комбинаций, отличных от кодовых N0 комбинаций будет очевидно E  N0. С другой стороны, это число не должно превосходить числа N – N0 всех возможных неразрешенных комбинаций. Следовательно, EN0 ≤ N – N0 и тогда

; , (3.2)

где S – кратность ошибки (число неверно принятых разрядов),

- число сочетаний возможных ошибок.


Для исправления однократной ошибки S = 1, = n и нижняя оценка

, т.к. N0 = 2n, то (3.3)

Это условие выбора длины кода m при заданной длине информационного сигнала n. Зная n, вычислив m, можно определить разрядность проверочных символов r = m – n. Для n = 4 (N0 = 24 = 16),
m = 7, r = 3 код (7,4); для n = 5 (N0 = 25 = 32), m = 9, r = 4 код (9,5).

Для исправления двукратных ошибок S = 2, .

Для n = 4 (N0 = 24 = 16), m = 10, r = 6 код (10,4); для n = 5 (N0 = 25 = 32), m = 11, r = 5 код (11,5).


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

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

Рассмотрим пример кодирования и исправления однократных ошибок групповым кодом Хемминга для n = 4 разрядных информационных блоков. Из условия (3.3.) следует, что m = 7, код (7,4) имеет семь разрядов, из них 4 информационных.

Построим "матрицу ошибок", т.е. переберем все возможные однократные ошибки (место ошибки определим вектором с одной единицей):

. (3.4)

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

а)

а1  а3  а5  а7 = 0

б)

а1 = а3  а5  а7







а2  а3  а6  а7 = 0




а2 = а3  а6  а7

(3.5)




а4  а5  а6  а7 = 0




а4 = а5  а6  а7




В качестве примера закодируем информационный блок 1010.

В выбранном 7 элементном блоке 1, 2, 4 разряды заняты под проверочные, а в 3, 5, 6, 7 разрядах запишем передаваемую информацию.

1

0

1




0







а7

а6

а5

а4

а3

а2

а1

Найдем проверочные символы из уравнения (3.5,б)

а1 = а3  а5  а7 = 0  1 1 = 0 а1 = 0

а2 = а3  а6  а7 = 0  0  1 = 1 а2 = 1

а4 = а5  а6  а7 = 1  0  1 = 0 а4 = 0


Теперь запишем закодированный блок

1

0

1

0

0

1

0

а7

а6

а5

а4

а3

а2

а1

число 1010010.

Допустим, что при приеме этого блока произошла ошибка в третьем разряде (т.е. мы приняли блок вида 1010110), тогда проверочные равенства (3.5,а) в приемнике дадут синдром ошибки:

а1  а3  а5  а7 = 0  1  1  1 = 1

а2  а3  а6  а7 = 1  1  0  1 = 1

а4  а5  а6  а7 = 0  1  0  1 = 0.

Полученный синдром 011 указывает, что ошибка произошла в третьем разряде, и, значит, третий разряд надо исправить (просто инвертировать на обратный знак). Так можно обнаружить и исправить любую однократную ошибку (в любом разряде).


3.3.4. Мажоритарное декодирование групповых кодов

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

Пример. Рассмотрим код (7,4), построенный в подразделе 3.3.3. На базе системы проверочных равенств для каждого информационного символа составляем свою систему проверочных равенств (для а7 первые три уравнения получаем из уравнения (3.5,а), четвертое получаем суммирование первых трех уравнений, пятое записываем, исходя из требования нечетного количества уравнений; для а6 первое и второе уравнения получаем из уравнения (3.5,а), третье уравнение получаем из нового первого уравнения путем замены члена а7 первым уравнением из столбца для а7 и сокращением двойных элементов, четвертое уравнение получаем аналогично третьему заменой во втором новом уравнении столбца а6 элемента а7 из первого уравнения столбца а7 и т.д.):

а7 = а1а3а5;

а6 = а2а3а7;

а7 = а2а3а6;

а6 = а3а5а7;

а7 = а4а5а6;

а6 = а1а2а5;

а7 = а1а2а3;

а6 = а1а3а4;

а7 = а7;

а6 = а6.

и т.д.

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

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




следующая страница >>