5. Краткие теоретические сведения

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

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

Но для представления N сообщений достаточно использовать число двоичных разрядов, равное:

k = [log₂N],

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

Например, при N = 13k = [log13] = 3,7 4 достаточно иметь 4 разрядадвоичного числа. При этом максимальное число возможных комбинаций 4-х разрядного двоичного числа составляет 2⁴ = 16. Следовательно, 3 комбинации двоичного числа, равные разности максимального числа возможных комбинаций и числа используемых сообщений, являются лишними и не используются для представления сообщений.

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

x_k-1, ... , x₁, x₀.

Каждая переменная может принимать только два значения 0 или 1. Каждый разряд двоичного числа имеет свой «вес». Нулевому значению любой переменной соответствует вес, равный нулю, а единичному значению разряда соответствует десятичное число, значение которого зависит о номера разряда и равно 2^k-1. Десятичный эквивалент двоичного числа равен сумме весов всех разрядов, имеющих единичное значение.

Так, двоичному 4-х разрядному числу 1001 соответствует десятичное число:

2³ + 0 + 0 + 2⁰ = 9.

Таким образом, каждому сообщению соответствует конкретное десятичное число, записанное в двоичной форме. Следовательно, при передаче по каналу связи какого-либо сообщения требуется без искажений передать и правильно принять соответствующее данному сообщению десятичное число.

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

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

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

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

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

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

Минимальное число d элементов, в которых одна кодовая комбинация двоичного кода отличается от другой, называется минимальным кодовым расстоянием данного кода d_min.

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

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

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

Кодовое расстояние между двумя любыми комбинациями двоичного кода определяется путем подсчета числа единиц, получаемых при сложении одноименных разрядов комбинаций по модулю 2. Сложение по модулю 2 обозначается символом  и производится по следующему логическому правилу:

1  0 = 1;

0  1 = 1;

0  0 = 0;

1  1 = 0.

Например, необходимо определить кодовое расстояние двух комбинаций значений 4-х разрядного двоичного кода, например: 1001 и 0101. Произведем поразрядное сложение по модулю 2: 1001  0101 = 1100. Из полученного результата сложения следует, что искомое число единиц равно 2, т.е. кодовое расстояние d = 2.

Допустим, что все комбинации с кодовым расстоянием d = 2 и более относятся к разрешенным комбинациям, но в одной из них при передаче произошло искажение одного разряда, например, вместо 0101 на приемной стороне получили 0001. Применяя к предыдущему примеру сложение по модулю 2, получим: 1001  0001 = 1000. Следовательно, принятая кодовая комбинация по отношению к одной из разрешенных имеет минимальное кодовое расстояние, равное 1, следовательно, она не может относиться к числу разрешенных комбинаций и является ошибочной.

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

Особенность построения кодовых комбинаций корректирующего кода заключается в том что в состав разрешенных комбинаций должны входить лишь такие, которые имеют по отношению друг к другу минимальное кодовое расстояние d_мин ≥ (m + s + 1), где s - число исправляемых ошибок.

Таким образом, чтобы обнаружить, а затем исправить единичную ошибку необходимо иметь d_мин = 3.

Например, имеем две разрешенные кодовые комбинации: 1001 и 0111. Произведем их сложение по модулю 2: 1001  0111 = 1110. Откуда следует, что сумма имеет кодовое расстояние d_мин = 3.

Допустим, при передаче второй комбинации произошла ошибка в ее младшем разряде, т.е. принята комбинация 0110. Осуществляя поразрядное сложение по модулю 2 разрешенных комбинаций с принятой комбинацией, получим: 0111 0110 = 0001, следовательно, d = 1; 1001 0110 = 1111, следовательно, d = 4.

Находим сумму кодовыхкомбинаций, имеющих минимальное кодовое расстояние: 0111  0110 = 0001.

Наличие только одной единицы в полученной сумме по модулю 2 указывает на то, что принятая кодовая комбинация искажена (реализуется функция обнаружения ошибки), а местонахождение ее в младшем разряде указывает, что в данном разряде произошла ошибка и его значение необходимо откорректировать путем замены значения младшего разряда принятой комбинации на противоположное. После корректировки сложение по модулю 2 дает число, состоящее из одних нулевых разрядов: 0111  0111 = 0000. Число 0000 говорит о верном исправлении искажения.

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

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

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

Код Бауэра имеет следующие характеристики:

- относительная избыточность кода R, равная отношению числа r контрольных разрядов к общей длинеn кода, равной (k + r), где k - число информационных разрядов исходного кода:

- минимальное кодовое расстояние d_мин = 2 при k = 2; d_мин = 3 при k = 3;d_мин = 4 при k = 4;

- число обнаруживаемых ошибокm = d_мин 1, соответственно при k = 2 m = 1, при k = 3m = 2, при k = 4m = 3. При этом может обнаруживаться и большее число ошибок. Так, например, при k = 2 может быть обнаружено до 67% двойных ошибок, а при k = 3– до 80% тройных и четвертных ошибок и все пяти- и шестикратные ошибки;

- максимальное число обнаруживаемых ошибок m при s = d_минm–1 соответственно равно m = 1 при d_мин = 3, m = 2при d_мин = 4.

Принцип построения инверсного кода. Допустим, что исходный код содержит n разрядов. Пронумеруем разряды инверсного кода следующим образом: k_n-1, k_n-2, ... , k₀, r_n-1, r_n-2, ... , r₀. Здесь символом k обозначены информационныеразряды, а символом r –контрольныеразряды исходного кода. Значение любого j-го разряда контрольной части равно сумме по модулю 2 всех разрядов информационной части, за исключением j-го ее разряда:

r_j = k_n-1  k_n-2  ... k_j+1  k_j-1 ... k₀.

В соответствии с указанной формулой для 8-ми разрядного инверсного кода запишем выражения для определения значений разрядов его контрольной части:

r₀ = k₃ k₂ k₁;

r₁ = k₃ k₂ k₀; (1)

r₂ = k₃ k₁ k₀;

r₃ = k₂ k₁ k₀.

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

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

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

Отсюда вытекает правило составления ФАЛ для разрядов синдрома в виде суммы по модулю 2 левой и правой частей соотношений (1):

i₀ = r₀ k₃ k₂ k₁;

i₁ = r₁ k₃ k₂ k₀;

i₂ = r₂ k₃ k₁ k₀; (2)

i₃ = r₃ k₂ k₁ k₀.

Для принятой без искажения кодовой комбинации значения всех четырех разрядов синдрома (2) должны быть равны 0, т.е. i₀ = i₁ = i₂ = i₃ = 0, что вытекает из правила составления соотношений (1). Если хотя бы один из разрядов синдрома не равен 0, то кодовая комбинация принята с ошибкой.

Наличие только одного ненулевого разряда синдрома указывает на то, что ошибка произошла в соответствующем контрольном разряде кодовой комбинации. Если ошибка произошла в k_j разряде информационной части кодовой комбинации, то все разряды синдрома, содержащие данный информационный разряд, кроме i_j -го будут равны единице.

Проверочные соотношения (2) являются ФАЛ и служат основой для синтеза декодирующего устройства.

Модифицированный код Бауэра. Он является одной из разновидностей кода с повторением и отличается от последнего тем, что при нечетном количестве единиц в исходном коде инвертируются первые (n – 1) старших разрядов контрольной части кода с повторением, а при четном – только последний младший разряд контрольной части кода с повторением.

Так, например, при использовании восьмиразрядного модифицированного кода Бауэра кодовая комбинация кода с повторением 1011 1011 преобразуется в кодовую комбинацию 1011 0101, а кодовая комбинация 1001 1001 - в кодовую комбинацию 1001 1000.

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

Характеристики модифицированного кода Бауэра:

- избыточность кода R = 0,5;

- минимальное кодовое расстояние d_мин = 4 при k ≥ 4;

- число обнаруживаемых ошибок без исправления m= d_мин –1;

- число обнаруживаемых и исправляемых ошибок при d_мин=3: m = s = 1;

- число обнаруживаемых и исправляемых ошибок при d_мин=4: m = 2, s =1.

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

Для 8-ми разрядного модифицированного кода Бауэра (k = r = 4) они принимают вид:

(3)

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

(4)

В случае правильного приема кодовой комбинации разряды синдрома согласно выражениям (3) и (4) должны иметь следующие значения: i₀ = i₁ = i₂ = i₃ = 0. Наличие единичных значений синдрома свидетельствуют о наличии ошибок:

- единичное значение только в одном из разрядов –присутствует ошибка в соответствующем контрольном разряде, который присутствует в уравнении разряда с единичным значением;

- три единичных значения – ошибка в соответствующем информационном разряде, значение которого не присутствует в разряде синдрома с нулевым значением;

- два или четыре единичных значений в синдроме – ошибка в двух и более разрядах.

Модифицированный код Бауэра нашел широкое применение в устройствах железнодорожной автоматики и телемеханики. Например, при передаче информации по каналам АЛС-ЕН в устройствах КЛУБ (комплексное локомотивное устройство безопасности), а также в унифицированной микропроцессорной системе автоматической блокировки АБ-УЕ.

Код Хэмминга. Он на практике имеетнаибольшее распространение среди корректирующих кодов. Код Хемминга позволяет исправлять все одиночные ошибки (при d_мин = 3), а также исправлять все одиночные ошибки и обнаруживать все двойные ошибки (при d_мин = 4), но не исправлять их.

В качестве исходного кода берут простой двоичный код на все сочетания с числом информационных символов k. К нему добавляют r контрольных символов. Общая длина кодовой комбинации будет равна: n = k + r.

Рассмотрим последовательность кодирования и декодирования сообщения с использованием кода Хэмминга.

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

2^r ≥ n + 1 = k + r + 1. (5)

По формуле (5) можно определить длину кода при заданном числе информационных или контрольных разрядов.

Допустим, что число информационных разрядов исходного кода равно 4. Условие (5) выполняется при r ≥ 3, так как 2^r– r =k +1 = 2³– 3 = 5.

Особенность построения кода Хэмминга заключается в том, что комбинация значений разрядов синдрома представляет собой двоичный код десятичного числа, указывающего номер разряда кодовой комбинации, в котором произошла ошибка. Для этого число разрядов синдрома должно быть равно числу контрольных разрядов, а сами контрольные разряды должны размещаться в кодовой комбинации на местах, кратных степени 2, т.е. на позициях 1, 2, 4 и т.д. Информационные разряды при этом располагаются на оставшихся позициях. Например, при семиразрядном коде Хэмминга (k = 4, r = 3) кодовая комбинация в общем виде будет выглядеть следующим образом:

r₁ r₂ k₄ r₃ k₃ k₂ k₁,

где k₄– старший (четвертый) разряд исходной кодовой комбинации двоичного кода, подлежащего кодированию; k₁– младший (первый) разряд.

Значения контрольных разрядов в коде Хэмминга определяются кодирующими устройствами по следующим уравнениям:

r₁ = k₄ k₃ k₁;

r₂ = k₄ k₂ k₁;

r₃ = k₃ k₂ k₁. (6)

Значения разрядов синдрома кодовой комбинации для ее декодирования определяются по формулам:

i₁ = r₁ k₄ k₃ k₁;

i₂ = r₂ k₄ k₂ k₁;

i₃ = r₃ k₃ k₂ k₁. (7)

Если комбинация значений разрядов синдрома принятой кодовой комбинации равна нулю (i₁ = i₂ = i₃ = 0), значит она принята без ошибок. В противном случае десятичный эквивалент двоичного кода синдрома i₃i₂i₁ равен номеру разряда кода Хэмминга, в котором произошла ошибка. Если ошибка произойдет в контрольном разряде, то двоичный код синдрома примет одно из следующих значений: 100, 010 или 001, что соответствует десятичным числам 1, 2 и 4, то есть номерам контрольных разрядов.

Модифицированный код Хэмминга с кодовым расстоянием d_мин = 4 получается добавлением к коду Хэмминга с кодовым расстоянием d_мин = 3 четвертого контрольного разряда r₄, определяемого путем суммирования по модулю 2 всех разрядов исходного кода Хэмминга:

r₄ = r₁r₂k₄r₃k₃k₂k₁ = k₄k₃k₂. (8)

Соответственно, значение четвертого разряда i₄ синдрома будет равно:

i₄ = r₄ k₄ k₃k₂r₁r₂k₁r₃.

Код Хэмминга (n = 8, r = 4) обнаруживает все 1, 2, 5 и 6 кратные ошибки, 80% 3-х и 4-х кратных ошибок и наиболее часто используется в телемеханических системах передачи информации.