Коды в системах телемеханики и связи
Необходимость в кодировании сигналов возникает в тех случаях, когда число сообщений N превосходит число качественных признаков Сигналов m(N>m). Если m-N, то, приписав каждому сообщению один из т признаков сигнала и посылая один элементарный импульс с данным признаком, можно передать все сообщения. Если же m<./V, то для передачи всех соббщений N приходится составлять комбинации из п элементарных импульсов с т качествами. Теперь сообщение выражается не одним импульсом, а комбинацией из п элементарных импульсов При этом число передаваемых сообщений N, равное числу комбинаций из п элементов, имеющих т различных признаков каждый, резко возрастает. Таким образом одна из задач кодирования состоит в обеспечении образования необходимого числа сообщений при ограниченном числе импульсных признаков т. На кодирование возлагается еще одна важная задача. Кодированный сигнал может приобрести свойства обнаружения, а иногда и исправления ошибок, которые возможны в процессе передачи информации, т е. кодирование повышает достоверность передачи сообщений.
Процесс преобразования сообщений в комбинации дискретных сигналов (кодовые комбинации) называют кодированием, а правило, по которому осуществляется это преобразование,- кодом. При математической записи кодовых комбинаций обычно пользуются цифрами или буквами. Каждой цифре или букве соответствует элементарный сигнал (импульс), наделенный определенными признаками (см. п. 2.2).
Коды в зависимости от числа различных качеств элементов кода подразделяют на двоичные (бинарные) т= 2 и многозначные т^ d. По принципам построения кодовых комбинаций различают равномерные и неравномерные коды. Равномерными называют такие коды, у которых все кодовые комбинации состоят из одинакового числа элементов (п= const). Их применяют в телемеханике. Наиболее общим критерием деления кодов является закон кодообразования, в соответствии с которым коды подразделяют на числовые, комбинаторные и корректирующие (помехоустойчивые).
Числовые коды отличаются тем, что их математической основой являются системы счисления. Число комбинаций в коде М = т», т. е. чем выше значность кода т, тем больше число комбинаций в коде при одном и том же п. Однако наибольшее распространение нашли двоичные коды т-2. Это объясняется тем, что технически наиболее просто реализуются устройства, имеющие два устойчивых состояния. Кодовые комбинации двоичного кода записываются в виде п-разрядного двоичного числа Для записи в двоичном коде данного числа сообщений N требуется иметь п разрядов м = [1о?2ЛД где [1о§2 означает ближайшее большее целое число. Ниже приведена запись кодовых комбинаций простого двоичного кода при Ы= 16 (п= 4).
За 0 и 1 следует принимать два качества какого-либо импульсного признака, например, при амплитудном признаке 0->-Ль I-WI2, а при частотном O^fi, 1-+-/Д.
Простой двоичный код не обладает свойствами самозащищен-ности при искажениях типа 1->-0 и 0->1. В самом деле, искажение любого символа в кодовой комбинации под воздействием помех в процессе передачи приводит к тому, что одна разрешенная кодовая комбинация переходит в другую разрешенную. Так, например, при передаче кодовой комбинации 1010 и искажении типа 1->0 в первом разряде приводит к тому, что будет принята другая кодовая комбинация 0010.
Комбинаторные коды основаны на применении математической теории соединений: перестановок Р
п
, размещений Лто и сочетаний Сто. К группе комбинаторных кодов относят также коды, использующие различные разновидности законов соединении.
В коде по закону перестановок Р
п
комбинации образуются из т символов и отличаются одна от другой только порядком следования символов. Число элементов во всех комбинациях п = tu = const, а общее число комбинаций N = m
При трех символах а, Ь, с (п = т — 3) возможны следующие перестановки: abc, acb, bac, bca, cab, cba.
Полное число комбинаций для различных т показано ниже.
т 3 4 5 6 7
Рп 6 24 120 720 5040
В коде по закону размещений Ат„ каждая комбинация состоит из п- т различных символов при полном их числе /ло> т. Соединения типа Ато различаются символами, входящими в них, или порядком их следования в комбинациях. Число возможных комбинаций:
N = АТ,,, = — т)
Так, при т
0
= 3 (например, а, Ь, с) и т = п = 2 возможны следующие размещения, ab, Ьа, ас, bc, cb, са.
Код по закону сочетаний Ст
а
отличается тем, что кодовые комбинации в нем образуются сочетанием из то по т элементов. Таким образом, в каждой комбинации число элементов п = т и различаются они только символами, их образующими. Общее число комбинаций
N = с;;;„ = m„/m(m
lt
— т)! |.
Так, при т
0
= 4(а, b, с, d) и п = т = 2 имеют место следующие комбинации: ab, ас, ad, bc, bd, cd.
Сменно-качественный код отличается наложением одного ограничения. Символы кода, которые расположены рядом, не могут быть одинаковыми, повторение же одинаковых символов допускается. Отсюда исключаются, например, такие комбинации, как abbc, ccab и т. д., а также структуры, как acb, abca и т. д., будут разрешенными. Сменно-качественные коды характеризуются числом символов т и полным числом элементов п. Полное число комбинаций при этом коде N = т(т — )‘~ «.
Пусть т — 3 (символы а, Ь, с) ил = 3. Тогда получим следующие комбинации (УУ=12): abc, acb, bac, bca, cab, cba, aba, аса, bcb, bab, cac, cbc.
Корректирующие коды имеют ту особенность, что они позволяют обнаружить, а при необходимости и исправить определенное число искажений, возникающих при передаче кодовой комбинации. Это достигается наложением определенных ограничений на закон составления или на число используемых кодовых комбинаций.
В таких кодах благодаря определенной избыточности сначала появляется возможность обнаружить,, т. е. определить факт наличия искажений в принятой комбинации. Вводя дальнейшие ограничения и усложняя структуру кода, можно получить возможность установить точное место ошибки и исправить ее, т. е. восстановить истинное сообщение.
Общий принцип обнаружения и исправления ошибок можно пояснить таким образом. Все множество комбинаций кода N разбивается на две группы: разрешенные комбинации (их число N
f
) и запрещенные комбинации (их число N — N
v
) или не используемые для передачи сообщений. Это разделение выполняется таким образом, чтобы искажение одного, двух или более элементов разрешенной кодовой комбинации превращало ее в запрещенную. При приеме это искажение будет обнаружено. Далее в результате сравнения принятой комбинации с разрешенными определяется та разрешенная комбинация, которая меньше всего отличается от принятой. Эту разрешенную комбинацию и считают истинной. Так исправляются ошибки. Принципы обнаружения и исправления ошибок наглядно иллюстрируются геометрическими моделями. Любой
л-элементный двоичный код (т== 2) можно представить в виде л-мерного куба, в котором каждая вершина отображает кодовую комбинацию, а длина ребра куба соответствует одной единице (рис. 2.3). Каждой вершине куба приписывают кодовую комбинацию по следующему правилу: на г»-м месте кодовой комбинации ставится О, если проекция этой вершины на г-ю ось координат равна 0, и 1, если проекция равна 1. Например, запишем кодовую комбинацию, соответствующую вершине А
4
. Проектируя эту вершину на ось х, мы получим единицу, на втором и третьем местах комбинации запишутся нули, так как проекции на оси х
2
и х
3
равны нулю. Таким образом, вся комбинация в точке А
4
запишется, как 100. В таком кубе расстояние между вершинами (кодовыми комбинациями) измеряется минимальным числом ребер, находящихся между ними. Это расстояние обозначается буквой d и называется кодовым расстоянием.
Кодовое расстояние d между двумя кодовыми комбинациями может быть определено как число одноименных разрядов с отличающимися символами. Например, d между комбинациями 0101001 и 1100111 равно четырем. Кодовое расстояние характеризует свойство помехозащищенности кодов, оно показывает, насколько одна разрешенная комбинация удалена от другой. Чем больше d, тем труднее помехам исказить посланную комбинацию так, чтобы она превратилась в другую разрешенную комбинацию, т. е. чтобы было принято ложное сообщение.
Для характеристики помехозащищенности свойств кода в целом существует понятие минимального кодового расстояния d
min
— это минимальное расстояние между двумя парами кодовых комбинаций, входящих в данный код. Проанализируем связь между величинами d
mm
и помехозащитными свойствами на примере двоичного (т= 2) трехразрядного (л = 3) кода. Если в этом коде использовать все восемь комбинаций в качестве разрешенных, то для этого кода d
min
=l и такой код не обладает помехозащитными свойствами. При уменьшении числа разрешенных комбинаций с восьми до четырех появляется возможность обнаружения одиночных ошибок. Для того чтобы реализовать эту возможность, выберем в качестве разрешенных такие кодовые комбинации, чтобы d
mm
— 2, например 111, 100, 001, 010.
Если в процессе передачи произошла одиночная ошибка, т. е. исказился один знак, то это будет обнаружено на приемной стороне. В самом деле, пусть передается кодовая комбинация 100 и во время передачи 1 исказилась в 0 в первом разряде. Тогда будет принята запрещенная кодовая комбинация 000, что говорит о наличии ошибки. Таким образом видно, что построение помехоустойчивого кода связано с недоиспользованием кодовых комбинаций, т. е. избыточностью. Уменьшение числа комбинаций приводит к повышению помехоустойчивого кода. Если еще больше ограничить число разрешенных комбинаций, то можно не только обнаруживать, но и исправлять ошибки. Выберем в трехмерном кубе (рис. 2.3, а) вершины, которые находятся друг от друга на расстоянии трех ребер (с/
т
,
п
= 3), например Л
0
(000) и А
7
(111)- Если в качестве разрешенных применять только эти две комбинации 000 и 111, то появляется возможность исправить одну ошибку или обнаружить две ошибки без возможности их исправления.
На рис 2 3, б показаны возможные искажения разрешенных кодовых комбинаций (рассматривается искажение только одного символа). Искаженные комбинации отличаются от исходных только одним символом, а от другой разрешенной комбинации — двумя символами. Поэтому на приемной стороне искаженную кодовую комбинацию отождествляют с исходной разрешенной. Разумеется, все эти рассуждения по исправлению искажений действительны только в том случае, когда вероятность двойных ошибок, а также ошибок большей кратности значительно меньше вероятности однократных ошибок.
Основными параметрами корректирующих кодов являются коэффициенты обнаружения ошибок /С
об
„ коэффициент избыточности /С
И1б
и корректирующая способность кода.
Коэффициент обнаружения ошибок показывает, какая часть от всех возможных ошибок обнаруживается данным кодом.
Корректирующая способность кода связана с минимальным кодовым расстоянием й
тт
следующими соотношениями:
Деем тичное число |
Простой двоимный разрядный код |
Контроль ный разряд |
Код с контролем ло четности |
Деся тичное число |
Простой двоичный разрядный код |
Контроль ный разряд |
Код с контролем но четности |
|
0 |
000 |
0 |
0000 |
4 |
100 |
1 |
1001 |
|
1 |
001 |
1 |
ООН |
5 |
101 |
0 |
1010 |
|
2 |
010 |
1 |
0101 |
6 |
по |
0 |
1100 |
|
3 |
011 |
0 |
оно |
7 |
111 |
1 |
1111 |
Использование геометрических моделей для построения корректирующих кодов при п> 3 затруднительно. Поэтому для построения многоразрядных помехоустойчивых кодов предусматриваются определенные правила. Рассмотрим ряд кодов, обеспечивающих обнаружение ошибок, которые применяют в телемеханике.
Код с контролем по четности — формируется дополнением простого двоичного «о-разрядного кода контрольным разрядом, в котором записывается 0 и 1 с тем, чтобы число единиц в кодовой комбинации было четным. Таким образом, общее число разрядов в передаваемой комбинации п = по+1. Кодовые комбинации для кода с контролем по четности при «о = 3 приведены в табл. 2.1.
Этот код содержит Л»р- 2″° комбинаций, имеет минимальное кодовое расстояние с1
тт
= 2. Коэффициент избыточности кода
Кнзб — 1 — 1йд.> 2″»/о?-> 2″»
+|
= 1 — Па/(П
0
+ 1).
На приемной стороне осуществляется проверка на четность. В принятых комбинациях подсчитывается число единиц. Если оно четное, то считается, что искажений не было. Этот код обнаруживает нечетное число искажений, его применяют в устройствах сопряжения каналов передачи данных с ЭВМ.
Коэффициент обнаружения для этого кода т. е. из тысячи искаженных комбинаций только в пяти ошибки не будут обнаружены.
Код с постоянным весом (равновесный код) выбирается из двоичного кода на все сочетания комбинаций с одинаковым числом единиц (/). Обще число разрешенных комбинаций такого кода
N
p
= С» = п/1(п- /)*]
Например, код С|(л = 5, число единиц — 3): 00111, 01011, 01101, 01110, 10011, 10101, 10110, 11001, ПОЮ, 11100.
Коэффициент избыточности данного кода
Кизб = 1 — ogiCn/og22″ = 1 — о%
г
С‘„/п
Правильность принятых комбинаций в кодах определяется подсчетом числа единиц и если, например, в коде С| принято не три единицы, то при передаче произошла ошибка. Код обнаруживает любые одиночные искажения, а также многие двойные, тройные и другие искажения.
В инверсном коде исходная л-разрядная двоичная комбинация дополняется другой также л-разрядной, составленной по определенному правилу. В линию посылается удвоенное число импульсов (2л). Правило образования кода следующее: если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную, а если нечетное, то в добавляемых л разрядах все нули превращаются в единицы, а единицы в нули. Таким образом комбинация 0101 в инверсном коде будет передана, как 01010101, а комбинация 1000 — как 10000111. Коэффициент избыточности этого кода /С
И
зб = 0,5.
При приеме кодовой комбинации выполняются две операции. Сначала суммируются единицы, содержащиеся в первых л элементах Если их число оказывается четным, то вторая группа из л элементов принимается без изменения, если нечетной, то вторая группа символов инвертируется (0-*-1 и 1-Ю). После этого обе зафиксированные комбинации сравниваются поэлементно и при выявлении хотя бы одного несовпадения делается вывод о наличии искажения. Ошибка в данном коде будет обнаружена только в том случае, если одновременно исказятся два элемента в исходной комбинации и соответствующие им два элемента в повторяемой комбинации.
В корреляционном коде каждый элемент исходного кода преобразуется в два, при этом 1 преобразуется в 10, а 0 в 01. Так, например, комбинация ОНО исходного кода в корреляционном коде запишется, как 01101001 У корреляционного кода так же, как и у инверсного, Кизб=
:
0,5. На приеме ошибка обнаруживается в том случае, если в парных элементах будут содержаться одинаковые символы, т. е. 00 или 11. Этот код обладает высокой помехоустойчивостью, ошибка не будет обнаружена только в том случае, если искажениям подвергнутся два рядом стоящих символа, соответствующие одному элементу исходного кода.
Циклические коды используют в аппаратуре передачи данных на железнодорожном транспорте. Они относятся к систематическим кодам, у которых при сложении по модулю 2 любого числа разре шенных комбинаций также получаются разрешенные, а проверочные элементы являются линейными комбинациями информационных (суммированием по модулю 2).
В циклических кодах при циклической перестановке элементов разрешенной комбинации также получается разрешенная комбинация. Циклический код задается производящим (образующим) полиномом, который определяет число проверочных элементов в комбинациях и закон их образования, т. е., в конечном счете, определяет свойства кода по обнаружению ошибок.
Двоичные комбинации формально можно записать полиномом фиктивной переменной х Например, комбинации 1110001 соответствует полином х
6
-)- х
5
+ х
4
-)- 1. Над этими многочленами можно выполнять все операции согласно законам алгебры, за исключением вычитания и сложения, которое осуществляется по модулю 2. Отличительной способностью разрешенных комбинаций данного циклического кода является то, что все они делятся без остатка на производящий полином.
Рассмотрим образование разрешенных комбинаций заданного циклического кода (л, к) с производящим полиномом д(х). Например задан код (7,4) с д(х)= х
3
+ х
2
— 1, тогда комбинация, которую необходимо закодировать в данном коде,
1011 + х + 1 = 0(х)
Кодирование заключается в циклическом сдвиге б(х) на г разрядов, что соответствует умножению этого полинома на х
г
. В данном случае г- 3, поэтому й(х)х
г
= (х
1
4- X 1)х’ = X
6
+ х
4
+ X
3
Полученный полином делим на производящий полином
(X
е
+ х
А
+ х»)/(х
3
+ X
2
+ 1) =
= х
3
+ х
2
+ Я (х)/<? (х),
где (х) = х~ + 1 — остаток от деления
Этот остаток прибавляем к полиному в (х) х
г
и окончательно получаем нужную нам разрешенную комбинацию х
ь
+ х
4
+ х
3
+ х
2
+ 1 — 1011 101,
где х
6
4- х
4
+ х
3
= й (х)х
г
, 1011 = к, 101 = г
В полученной комбинации четыре информационных и три проверочных элемента. Она без остатка делится на я(х)= х
3
— х
2
4-1.
Искажение комбинации можно представить как результат сложения неискаженной комбинации» и комбинации ошибки, которая также может быть записана полиномом. Ошибка не будет обнаружена, если полином ошибки без остатка делится на <?(х). Это возможно только в том случае, если степень полинома ошибки выше степени <?(х). Следовательно, циклический код надежно обнаруживает пакеты (группы) ошибок длиной, равной или меньшей степени ^(х), т. е. числа проверочных разрядов г.
⇐
Качественные признаки импульсов тока
|
Автоматика, телемеханика и связь на железнодорожном транспорте
|
Способы разделения сигналов и их элементов
⇒