Главная Минимаркер Железнодорожный транспорт Минимаркер Автоматика, телемеханика и связь на железнодорожном транспорте (АТС) Минимаркер Коды в системах телемеханики. Классификация и характеристики кодов

Коды в системах телемеханики. Классификация и характеристики кодов

В телемеханических системах сообщения передаются по схеме (рис. 1).

Схема передачи сообщений

Рис. 1 Схема передачи сообщений

На пункте управления сообщение «включить объект 1» преобразуется в линейный сигнал (три импульса тока положительной полярности). Этот процесс называется шифрацией или кодированием. Таким образом, кодирование – построение сигнала по определенным правилам. На контролируемом пункте происходит обратное преобразование линейного сигнала в сообщение. Этот процесс называется дешифрацией или декодированием.

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

В зависимости от длины кода n (число импульсов тока в кодовом слове) различают одноэлементные и многоэлементные коды. В одноэлементных кодах n = 1, и сообщение несет один импульс тока. Эти коды используют в системах телемеханики с разделительной и распределительной селекциями. В многоэлементных кодах n > 1 и сообщение несут n-импульсов тока. Их используют при качественно-комбинационной и кодовой селекциях.

В зависимости от основания кода k (число качеств импульсов тока) различают двоичные (двухпозиционные) и многопозиционные коды. Двоичные коды имеют два качества импульсов тока (k = 2). У многопозиционных кодов k > 2. Наиболее распространены двоичные коды, так как они имеют наиболее простую кодирующую и декодирующую аппаратуру. В дальнейшем будем рассматривать двоичные коды и качества импульсов тока в них обозначать 0 и 1 (это могут быть отрицательная и положительная полярность, малая и большая амплитуда тока и др.).

Важнейшей особенностью кодов является их классификация по помехоустойчивости. В зависимости от помехоустойчивости коды бывают обыкновенные и корректирующие. Обыкновенные коды не обеспечивают защиту информации от искажений в результате воздействия помех в линиях связи. Например, на пункте управления формируется трехэлементное кодовое слово в двоичном коде с амплитудными качествами 010 (рис. 2). Из-за помех в линии связи подавляется амплитуда второго импульса, и на контролируемый пункт поступает слово 000. В результате искажается информация и ложно включается объект 1 вместо объекта 3.

Искажение кодового слова

Рис. 2 Искажение кодового слова

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

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

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

Для оценки кодов используют две основные характеристики:

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

- избыточность кода R

R = n/m,

где n - число элементов кода; m - минимальное число элементов кода, необходимое для передачи S - сообщений.

Обыкновенные коды

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

S = 2n,

т.е. обыкновенный двоичный код есть множество всех n - разрядных двоичных чисел. Например, трехэлементный код имеет емкость

S = 23 = 8

В табл. 1 представлены кодовые комбинации трехэлементного двоичного кода.

Таблица 1

кодовые комбинации трехэлементного двоичного кода

Если надо передать S сообщений, то число разрядов обыкновенного двоичного кода должно быть:

число разрядов обыкновенного двоичного кода,

где kod_f2 - обозначение ближайшего к kod_f3 целого числа kod_f4.

Например, если S = 50, то kod_f5.

Эта формула определяет минимальное число элементов кода, необходимое для передачи S сообщений. Избыточность обыкновенного кода

Избыточность обыкновенного кода.

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

К классу обыкновенных кодов также можно отнести коды Шеннона-Фано, Хаффмена, Грея и др.

Избыточные коды

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

Общий принцип коррекции ошибок в коде можно пояснит следующим образом. Все множество комбинаций кода N делится на две группы: разрешенные для передачи кодовые комбинации (их число равно Nр) и запрещенные (их число равно N – Np). Распределение происходит таким образом, чтобы искажение одного, двух или более символов разрешенной комбинации превращало ее в запрещенную, а при приеме такой комбинации это искажение было бы обнаружено.

Предположим, что нам необходимо передать четыре сообщения. Обыкновенный код в этом случае должен иметь kod_f7 разряда. Введем еще один избыточный разряд и для передачи четырех сообщений применим трехэлементный код. С помощью трехэлементного кода мы можем передать S = 23 = 8 > 4 сообщений. Разобьем восемь слов кода на два непересекающихся подмножества.

Два непересекающихся подмножества

Если вследствие искажения разрешенное кодовое слово переходит в запрещенное, то ошибка обнаруживается, если же разрешенное слово переходит в разрешенное, то ошибка не обнаруживается, например:

kod_f9

Числу искаженных разрядов дали название – кратность ошибки, и условно обозначают буквой «г». В приведенных примерах кратность ошибок г = 1 и г = 2. Способность кода находить или исправлять ошибки определяется минимальным кодовым расстоянием. Кодовое расстояние или расстояние по Хэммингу между двумя словами – это число разрядов, в которых символы слов не совпадают. Если длина слова n, то кодовое расстояние может принимать значение от 1 до n. Минимальное кодовое расстояние данного кода – это минимальное количество разрядов, которыми различаются два кодовых слова. Слова 001 и 010 имеют кодовое расстояние d = 2. В большинстве случаев, чтобы избыточный код позволял находить ошибки кратностью r, должно выполняться следующее условие

kod_f10,

а для исправления r-кратной ошибки условие

kod_f11.

Допустим, необходимо передать те же четыре сообщения, но с исправлением ошибок кратности 1. При этом кодовое расстояние должно быть

kod_f12.

Увеличим избыточность кода и применим пятиэлементный код. Количество кодовых слов, которое можно передать с помощью пятиэлементного кода S = 4 < 25 = 32.

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

kod_f13

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

В большинстве случаев для одновременного нахождения ошибок кратностью r и исправления ошибок кратностью q должно выполняться условие

kod_f15,

где r - кратность ошибок исправления, q - кратность ошибок обнаружения, причем kod_f16.

Код с проверкой четности

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

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

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

kod_f17

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

kod_f18

Характеристики кода

Характеристики кода.

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

Равновесный код

У этого кода все кодовые слова имеют постоянное число единиц. Поэтому его называют кодом «m из n», т.к. каждое слово имеет m единиц из n - разрядов. Число m называют весом кода. Данный код относится к классу блочных неразделимых кодов. Минимальное кодовое расстояние dmin = 4. Параметры кода

Параметры кода.

Рассмотрим, например, код «2 из 4». Емкость этого кода S = C24 = 6, т.е. имеется шесть разрешенных кодовых комбинаций:

kod_f21

При приеме декодер подсчитывает число единиц и, если оно равно m (в данном случае m = 2), то сообщение принимается. Код обнаруживает ошибки, нарушающие вес. Это все одиночные ошибки:

kod_f22

все ошибки нечетной кратности, а также некоторые ошибки четной кратности

kod_f23

Не обнаруживаются ошибки четной кратности, у которых число искажений вида kod_f24 равно числу искажений вида kod_f25.

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

Корреляционные коды

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

kod_f26

Он является разделимым. Первый и второй разряды можно считать информационными, а третий и четвертый - контрольными. Параметры кода

Параметры кода

При приеме необходимо сравнивать одинаковые элементы обеих частей кода и, если они совпадают, то сообщение принимается. Декодер в этом случае состоит из декодера обыкновенного кода и схемы сравнения. Минимальное кодовое расстояние dmin = 2. Не обнаруживаются только ошибки четной кратности, в которых присутствуют искажения одинаковых разрядов:

kod_f28

В данном примере обнаруживается 80 % всех ошибок.

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

kod_f29

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

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

kod_f30

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

Код с суммированием (код Бергера)

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

Код с суммированием является разделимым и строится по следующим правилам:

1. Сообщения кодируются обыкновенным кодом. Число информационных разрядов Число информационных разрядов, где N - число передаваемых сообщений;

2. Число контрольных разрядов Число контрольных разрядов. Пусть N = 8, тогда

kod_f33

3. В контрольных разрядах записывается двоичное число, десятичный эквивалент которого равен числу нулей в информационных разрядах:

Информационные разряды Контрольные разряды

Информационные и контрольные разряды

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

Докажем, что код с суммированием обнаруживает все кратные однонаправленные ошибки. Двойная ошибка вида kod_f24d:

kod_f34

обнаруживается, так как искажения kod_f24e в информационных разрядах уменьшают число нулей, в то время как искажения kod_f24f в контрольных разрядах увеличивают число нулей в них. Это противоречие гарантирует обнаружение всех однонаправленных ошибок вида kod_f24g любой кратности. Аналогично обнаруживаются и однонаправленные ошибки другого вида, так как искажения kod_f25f в информационных разрядах увеличивают число нулей, а искажения kod_f25g в контрольных разрядах уменьшают число нулей в них:

kod_f35

Код Хэмминга

Среди кодов с исправлением ошибок наибольшую популярность в практике получил код Хэмминга. Код Хэмминга исправляет ошибки кратности 1 и является разделимым. Число информационных разрядов

kod_f36,

где N - число сообщений, которое нужно передать. Длина кода определяется из неравенства

kod_f37,

тогда число контрольных разрядов k = n – m.

Рассмотрим построение кода Хэмминга на следующем примере. Пусть необходимо передать слово 10110, представленное в обыкновенном коде. С помощью пятиэлементного обыкновенного кода можно передать 25 = 32 слова. Тогда длина кода определится следующим образом:

kod_f38.

В нашем случае n = 9, т.е. искомое слово Хэмминга имеет девять разрядов, из них контрольных разрядов, соответственно k = 9 – 5 = 4.

kod_f39

За контрольные разряды принимаются разряды, десятичный номер которых равен степени числа 2. Это разряды a1, a2, a3, a4. Двоичные номера контрольных разрядов (0001, 0010, 0100, 1000) имеют только одну единицу. Остальные разряды являются информационными, и в них записывается передаваемое слово.

Для определения значения контрольных разрядов, составляют контрольные суммы Si.

Сумма Si – это сумма по модулю два значений разрядов, двоичные номера которых имеют единицу на i-м месте справа.

kod_f40

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

Тогда

kod_f41

В нашем примере

kod_f42.

Следовательно, процедура кодирования закончена и получено следующее соответствие 10110 – 011001100.

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

kod_f43

двоичное число S4S3S2S1 = 01012 = 510, т.е. произошла ошибка в 5 разряде. Исправление ошибки состоит в изменении значения искаженного разряда на противоположное.

Для определения параметров кода Хэмминга выразим число m через n:

kod_f44.

Отсюда

kod_f45.

Тогда

kod_f46.

Описанный код имеет кодовое расстояние d = 3. Этот код позволяет исправлять ошибки кратности 1 и находить ошибки кратности 2. Однако одновременно исправлять одиночные и определять двойные ошибки код не может, так как эти ошибки могут оказаться неразличимыми. Например, в передаваемом слове происходит двойная ошибка в разрядах а2 и а5, и принятое слово имеет вид 001011100.

Контрольные суммы соответственно

kod_f47

Такой же результат получится, если произойдет одиночная ошибка в седьмом разряде и будет принято слово 011001000. В этом случае

kod_f48

Чтобы код Хэмминга одновременно исправлял одиночные ошибки и обнаруживал двойные, необходимо придать ему кодовое расстояние d = 4. Для этого добавляется еще один десятый контрольный разряд, который проверяет четность единиц в информационных и основных контрольных разрядах: kod_f49:

kod_f50

При приеме данного кода возможно:

- ошибки нет – все суммы Si = 0, и проверка на четность подтверждается;

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

- есть ошибка дополнительного контрольного разряда, и он исправляется – все суммы Si = 0, и проверка на четность не подтверждается;

- есть двойная ошибка; она находится, но не исправляется - хотя бы одна сумма kod_f51p, и проверка на четность подтверждается.


© 2013 - 2017 Учебно-образовательный портал "Все лекции"
Материалы, представленные на страницах нашего сайта, созданы авторами сайта, присланы пользователями, взяты из открытых источников и представлены на сайте исключительно для ознакомления. Все авторские права на материалы принадлежат их законным авторам.
Разработка сайта - Скобелев Алексей





Яндекс.Метрика