КОДИРОВАНИЕ

В табл. 51 показаны уровни, которые может превысить сигнал на выходе средства измерений. При этом не сущест­венно, является ли он постоянным, меняющимся во времени или его значение выбрано в фиксированный момент времени п · Δ t. Измерительная информация заключается в том, какой уровень превышен сигналом. Таким образом, информация о значении сигнала оказывается дискретной. Переход к ней называется квантованием, а сами уровни — уровнями кванто­вания сигнала. При равных промежутках между уровнями квантование называется равномерным, при неравных — неравномерным. Наибольшее распространение в технике по­лучило равномерное квантование по уровню.

Если будет зафиксировано, что сигнал превысил i-и уро­вень (но не достиг i + 1-го), то его значение

где значение поправки Q может быть любым в пределах от 0 до ΔХ = Х+1 — X,. Ситуационная модель поправки показана на рис. 166. Величина ΔХ называ­ется шагом квантования. Дефи­цит информации о значении поп­равки приводит к потере точнос­ти. С учетом поправки

При заданных и_х и диапазоне изменения сигнала от 0 до Х_max число уровней или ступеней квантования определяется по фор­муле

Уровни квантования могут быть обозначены какими-либо символами или пронумерованы, как показано в табл. 51, в десятичной или любой другой системе счисления. Такая опера­ция называется кодированием. Символы или цифры предс­тавляют собой кодовые элементы. В десятичном коде это 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; в двоичном — 0 и 1. Двоичный код проще десятичного и легче реализуется в технических систе­мах. Поэтому он получил преимущественное распространение.

Любое число в двоичной системе счисления записывается в виде суммы

где с, — цифры двоичной системы счисления (0 или 1), стоя­щие в соответствующих разрядах; п — число разрядов. Прави­ла суммирования в двоичной системе чрезвычайно просты:

0+0=0; 0+1=1; 1+0=1; 1+1= 10. Примеры приведе­ны в табл. 51. Так, в частности, число 13 в двоичной системе записывается 1101, что соответствует сумме 1·2³ + 1·2² +0·2¹ +1·2⁰.

Из приведенных в табл. 51 примеров видно, что кодовые комбинации (совокупность кодовых элементов) могут иметь одинаковую или неодинаковую длину. Соответственно разли­чаются равномерные и неравномерные коды. Число знаков в кодовой комбинации, равное числу разрядов, определяет значность равномерного кода. Например, пятизначный код Бодо, предназначенный для кодирования букв алфавита, поз­воляет образовать не 16, как четырехзначный (см. табл. 51), а 32 кодовых комбинации одинаковой длины. Вообще же, максимальное число, кодируемое n- разрядным двоичным ко­дом,

Уровни квантования совсем не обязательно должны кодироваться посредством их нумерации в двоичной системе счисления. В этом случае при переходе сигнала на сосед­ний уровень возможно изменение двоичных кодовых эле­ментов сразу в нескольких разрядах. Это повышает вероят­ность ошибок, называемых ошибками считывания. Во избежание этих ошибок применяются правила образования кодовых комбинаций, при которых соседние комбинации могут отличаться цифрой только в одном разряде. Такие коды получили название отраженных. Наиболее распростра­ненным из них является код Грея (см. табл. 51), который легко преобразуется в двоичный код по следующему прави­лу: первая единица со стороны старших разрядов остается без изменения; последующие цифры остаются без изменения, если число единиц слева четно, и инвертируются — если нечетно.

Очень широкое распространение получило двоичное коди­рование каждой цифры десятичного числа в отдельности. Так как цифр всего 10, то для этого необходимы 10 кодо­вых комбинаций, 3-х значный двоичный код позволяет обра­зовать их 8, а 4-х значный — 16. Таким образом, первый не годится, а второй дает 6 лишних комбинаций. Так как в ка­честве лишних могут рассматриваться любые 6 из 16 воз­можных 4-х значных комбинаций, то открывается возмож­ность построения большого числа самых разнообразных кодов. Они называются двоично-десятичными, причем в наз­вании указываются коэффициенты, на которые нужно ум­ножать соответствующие кодовые элементы для того, что­бы в сумме получалась кодируемая цифра. Так, при исполь­зовании кода 4—2—2—1 число 138 будет закодировано в ви­де 0001 0011 1110, что означает

4·0+2·0+2·0+1·1= 1;

4·0+2·0+2·1+1·1=3;

4·1+2·1+2·1+1·0=8.

Пример использования этого кода приведен в табл. 51. Как можно заметить, такое кодирование является неоднознач­ным. Цифра 3 может быть закодирована в виде 0101, цифра 4 — в виде 1000, 5 — в виде 1001 и т.д. Необходимая однознач­ность достигается только соответствующим построением уст­ройств кодирования и декодирования. Единственным одно­значным двоично-десятичным кодом является код 8 - 4 -2-1.

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

N_кк=2ⁿ

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

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

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

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

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

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

Порядок построения кода Хэмминга следующий.

1. Определяется необходимое количество информацион­ных k и проверочных т разрядов. Число проверок в дальней­шем будет равняться числу проверочных разрядов r , а резуль­тат каждой проверки будет обозначаться символом 0 или 1. Записанные справа налево символы образуют число в двоич­ной системе счисления, соответствующее номеру искаженно­го разряда. Так как это число не может быть меньше k, а число разрядов в нем равно r, то должно выполняться усло­вие

R—1≥ k.

2. Все проверки заключаются в вычислении суммы по мо­дулю 2 кодовых элементов в соответствующих разрядах ко­довой комбинации. При первой проверке выбираются те разряды, двоичный номер которых содержит единицу в пер­вом разряде, т.е. 1, 3, 5, 7, 9-й ... . При второй проверке выбираются разряды, двоичный номер которых содержит 1 во втором разряде, т.е. 2, 3, 6, 7, 10-й ... . При третьей про­верке выбираются 4, 5, 6, 7,12,13-й . . . разряды и т.д.

3. Место расположения проверочных разрядов в кодовой комбинации в принципе может быть выбрано произвольным, однако при выбранном правиле проверок проверочные симво­лы (0 или 1) удобнее размещать в разрядах, номера которых равны целой степени числа 2, т.е. в 1, 2, 4, 8-м и т.д.

4. Способ заполнения проверочных разрядов определяется правилом проверки корректирующего кода.

Пример 80. Построить код Хэмминга для чисел от 0 до 15 и вос­пользоваться им для коррекции кодовой комбинации.

Решение. 1. Так как N_p = 16, то необходимое число информацион­ных разрядов k = 4.

2. Исходя из условия 2^r— 1 ≥k, необходимое число проверочных разрядов r = 3. Ход Хэмминга, следовательно, должен иметь п = k + r = 7 разрядов.

3. В соответствии с рекомендацией 3 в качестве проверочных удоб­но выбрать 1, 2 и 4-й разряды. Остальные (информационные) должны использоваться для размещения в них чисел от 0 до 15 в двоичной системе счисления.

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

Десятичное Кодовая

число комбинация

0 0000000

1 1101001

2 0101010

3 1000011

4 1001100

5 0100101

6 1100110

7 0001111

8 1110000

9 0011001

10 1011010

11 0110011

12 0111100

13 1010101

14 0010110

15 1111111

5. Рассмотрим кодовую комбинацию 0111110. В кодовой таблице ее нет, так что в одном из разрядов допущена ошибка (возможностью многократных ошибок по-прежнему будем пренебрегать). Первая про­верка дает 0Å1Å1Å0=0; вторая —1Å1Å1Å0= 1; третья — 1Å1Å1Å0=1. Записывая результаты проверок, справа налево, устанавливаем, что искажен кодовый элемент в 110 (шестом) разря­де. Таким образом, правильной является кодовая комбинация 0111100, соответствующая числу 12.

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

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

l_cp= å_kP_kl_k ,

где суммирование производится по всем кодируемым значе­ниям сигнала; P_k — вероятность k-гo значения, a l_k¾длина (число разрядов) соответствующей ему кодовой комбина­ции. Наиболее экономичным (эффективным) является код, средняя длина кодовой комбинации у которого минималь­на. Такой код, синтезированный по критерию

å_kP_kl_k = min,

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

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

Пример 81. В дискретный канал связи измерительной системы поступает сигнал от промежуточного измерительного преобразова­теля, подчиняющийся нормированному нормальному закону распре­деления вероятности. Измерительная информация содержится в кор­реляционной функции сигнала. Построить код Шеннона-Фэно для пе­редачи значений сигнала после его дискретизации.

Решение. 1. Сигнал Х (t) в каждый момент времени характеризу­ется уровнем квантования, который может быть положительным или отрицательным. Разобьем сначала весь диапазон изменения сигнала на 10 равных поддиапазонов, ограниченных пятью положительными и пятью отрицательными уровнями. После этого поддиапазоны, приле­гающие к нулевому уровню, дополнительно разобьем пополам. Полу­чим всего 12 поддиапазонов. Вероятность того, что сигнал Х (t) ока­жется в одном из поддиапазонов, равна разности значений функции Лапласа на границах поддиапазона. Например, вероятность того, что сигнал Х (t) окажется в поддиапазоне между 4-м и 5-м уровнями, равна L (5) — L (4) ≈ 0,001, между 1-м и 2-м -L (2) -L (1) ≈ 0,136,между уровнями 0 и 1/2 - L (-1/2)-L (0) ≈0,192, между уровнями -1 и -1/2 - L (-1/2) -L (-1) ≈0,149 и т.д. Все сформированные под

диапазоны и вероятности того, что сигнал Х (t) окажется в каждом из них, приведены в порядке убывания в табл.52.

2. При построении кода Шеннона-Фэно все возможные варианты сначала делятся на две группы так, чтобы суммы вероятностей в каждой изних были по возможности одинаковы (см. табл. 52). Всем вариантам I группы в качестве первого символа в кодовой комбинации припи­сывается 0 а вариантам II группы - I. Затем каждая группа в свою оче­редь разбивается на две подгруппы с примерно одинаковыми суммар­ными вероятностями, процедура присвоения символов повторяется и т.д.

Кодовая таблица для рассматриваемого примера представлена первой и последней графами в табл. 52.

Таблица 52

Поддиапазон между уровнями	Вероятность попадания сигнала в поддиапазон	Деления на группы	Кодовая комбинация
II I II I III II I II II I I II I III I II I II II I I III I II I II I I I I 0 . . . 0,5   0 . . . – 0,5   0,5 . . . 1   - 0,5 . . . - 1   1 . . . 2   - 1 . . . - 2   2 . . . 3   -2 . . . - 3   3 . . . 4   - 3 . . . - 4   4 . . . 5   - 4 . . . - 5	0,192   0,192   0,149   0,149   0,136   0,136   0,021   0,021   0,001   0,001   0,001   0,001