Глава 21. Устройства защиты от ошибок в передаваемой информации |
292 |
аппаратуры.
Опасность возникновения внутренних наводок возросла с внедрением БИС, СБИС особенно средней и большой сложности, вплоть до микропроцессорных наборов. Из-за увеличенной плотности элементов и схем сами ИС и межсоединения становятся источниками помех, которые передаются через возросшие паразитные емкости и индуктивности между проводниками или через проводимость изоляции. В зависимости от того, какой из этих параметров определяет в основном величину тока наводки, различают емкостные наводки, электромагнитные и гальванические. Величину тока электрической помехи Iп , наведенной через емкостную паразитную связь величиной С от источника помехи с амплитудой Uп и частотой fп, можно определить из выражения
Iп=2Uпπ fпС.
Аппаратура считается помехоустойчивой, если при воздействии помех допустимого уровня она продолжает выполнять свои функции без искажения информации (без ошибок).
21.2. Краткая характеристика способов защиты от ошибок
Основным способом повышения верности передачи дискретных сообщений является введение в передаваемую последовательность избыточности с целью обнаружения и исправления ошибок в принятой информации. Все устройства защиты от ошибок (УЗО) делятся на две группы: симплексные (без обратной связи) и дуплексные (с обратной связью).
В симплексных УЗО повышение верности может быть достигнуто тремя способами:
-путем многократного повторения символов,
-одновременной передачей одной и той же информации по нескольким параллельным каналам,
-применением кодов, исправляющих ошибки.
Многократное повторение является наиболее простым способом повышения верности, который состоит в том, что передатчик посылает в канал нечетное число раз одну и ту же информацию, а на приемной стороне производится сравнение между собой одноименных кодовых комбинаций (либо одноименных двоичных разрядов). Потребителю выдается тот символ (или бит), который был принят большее число раз (мажоритарный метод). Избыточность информации растет пропорционально количеству повторений одних и тех же символов, аналогично возрастают и затраты времени на передачу массива.
Вероятность ошибочного приема символа Ркк, состоящего из nк - разрядной комбинации, при трехкратном повторении и посимвольном сравнении не превышает величины, определяемой по формуле
Ркк≈ 3nк2Ро,
где Ро - вероятность ошибочного приема единичного элемента.
При пятикратном повторении nк - элементной комбинации эта вероятность равна:
Ркк≈ 10nк2Ро3.
При поразрядном сравнении принимаемых символов, состоящих из nк бит, вероятность ошибочной регистрации кодовой комбинации при трехкратном и пятикратном повторении соответственно равна
Ркк≈ 3nкРо2; Ркк≈ 10nкРо3.
Эти формулы справедливы при независимых ошибках в дискретном канале. При пакетировании ошибок (объединении одиночных ошибок в пакеты, в пачки) вероятность поражения соседних символов, а тем более бит, высока, что может привести к значительному снижению помехоустойчивости. Для устранения этого явления производят декорреляцию ошибок, увеличивая интервал между повторяемыми символами (битами), то есть следует повторять не отдельные символы блока, а их группы либо весь блок. Такой алгоритм пере-
Глава 21. Устройства защиты от ошибок в передаваемой информации |
293 |
дачи приводит к усложнению аппаратуры и увеличению временной задержки между передачей данных от источника и получением их потребителем.
Способ одновременной передачи по нескольким каналам по помехоустойчивости эквивалентен способу многократной передачи. Он предусматривает наличие нечетного количества каналов, по которым передаются одни и те же кодовые последовательности. На приемной стороне используется мажоритарный прием. Основное требование таких систем: наличие параллельных каналов с независимыми ошибками. Для обеспечения этого требования каналы связи должны быть разнесены географически или выбираться в разных линиях связи. Недостатком этого способа является резкое повышение стоимости системы передачи данных (СПД).
Наибольшей эффективностью в симплексных СПД обладает способ защиты от ошибок в передаваемой информации, основанный на использовании кодов с исправлением ошибок, называемых также исправляющими или корректирующими кодами. В таких системах передаваемый блок кроме информационных единичных элементов, полученных от источника информации, содержит и избыточные проверочные биты, формируемые кодирующим устройством на основании информационных разрядов по определенным правилам. На приемной стороне декодирующим устройством по тем же правилам осуществляются аналогичные проверки, при которых учитываются и проверочные элементы. В результате проверки определяется номер позиции в принятом блоке, значение которой необходимо в процессе исправления проинвертировать. Вероятность ошибочного приема символа зависит не только от вероятности ошибки в дискретном канале, но и от применяемого помехоустойчивого кода.
Помехоустойчивыми кодами называются коды с избыточностью, позволяющие обнаруживать и исправлять ошибки, возникающие в результате воздействия помех в принимаемых кодовых последовательностях. Корректирующая способность кода зависит от кодового расстояния d, численно равного минимальному числу элементов, которыми отличается любая кодовая комбинация от другой. В общем случае
d=tо +tи +1,
где tо и tи - число обнаруженных и исправленных ошибок соответственно, причем обязательно tо≥ tи. Если код только обнаруживает ошибки, то d=tо+1, а в случае только исправления d=2tи+1. Количество проверочных элементов r корректирующего кода зависит от вида кода, а число информационных элементов k=n-r, где n-длина двоичной последовательности, кодируемой помехоустойчивым кодом. Отношение r/n называется коэффициентом избыточности кода.
Пример 21.1. Выбрать способ защиты от ошибок, обеспечивающий вероятность побайтной передачи Ркк<1·10-6 при передаче данных по симплексному двухпроводному телефонному каналу связи со скоростью 1200 бит/с при условии, что ошибки на выходе дискретного канала группируются в пакеты длиной не более 12 бит, а минимальный интервал между пакетами составляет 3 с. Вероятность ошибки по элементам на выходе дискретного канала Ро<1·10-4.
Для исправления ошибок кратностью 12 наиболее целесообразно в данном случае применить способ многократной передачи информации. Так как пачка ошибок может поразить 3 байта, то повторять следует не менее трех знаков. При трехкратном повторении и поэлементном сравнении вероятность ошибки регистрации знака равна:
Ркк≈ 3nкРо2≈ 3·8(1·10-4)2=0,24·10-6<1·10-6.
Максимальная задержка выдачи информации потребителю при трехкратном повторении составит tз=24τ о=24·0,83≈ 20 мс, что вполне приемлемо для технических нужд.
21.3.Обнаруживающие коды - с проверкой на четность и итеративный код
Одним из простых кодов, позволяющих обнаруживать одиночные ошибки, является код с проверкой на четность. Он образуется путем добавления к передаваемой комбинации, состоящей из k информационных символов неизбыточного кода, одного контрольного бита
Глава 21. Устройства защиты от ошибок в передаваемой информации |
294 |
так, чтобы общее количество единиц в передаваемой комбинации было четным. В итоге общее количество элементов в передаваемой комбинации n=k+1. На приемной стороне производят проверку на четность. При четном числе единиц предполагается, что ошибок нет, и потребителю выдается k бит, а контрольный элемент отбрасывается. Аналогично строится код с проверкой на нечетность.
Кодирующие и декодирующие устройства кодов с защитой на четность - самые простые. Формирование контрольного бита осуществляется сумматором по модулю 2 (Т-триг- гером). Передаваемая в канал двоичная комбинация одновременно подается на вход Т-триг- гера. На соответствующей временной позиции импульсом с распределителя производится опрос сумматора, и при единичном состоянии последнего в канал подается “1” (дополняющая переданную последовательность до четного числа), а при нулевом - “0”. Аналогичная процедура производится на приемной стороне. Нулевое состояние Т-триггера в конце приема блока свидетельствует об отсутствии одиночных ошибок.
Минимальное кодовое расстояние кода d=2, поэтому код позволяет обнаруживать все одиночные ошибки, а кроме того, все случаи нечетного числа ошибок (3, 5, и т.д.).
Вероятность необнаружения ошибок для кода с проверкой на четность зависит от длины
блока n и вероятности ошибочного приема единичного элемента Р0:
Ркк≈ Сn2Ро2(1-Ро)n-2, Cnl=n!/[l!(n-l)1],
где Сnl - число сочетаний из n по l.
Как показывают расчеты по этим формулам, для обеспечения вероятности ошибки по символам менее 1·10-6 допустимая длина кодовой комбинации составляет несколько байт.
Итеративный код характеризуется наличием двух или более систем проверок внутри каждой кодовой комбинации, согласно ГОСТ 20687-75 он строится следующим образом. К семиэлементному коду КОИ-7 добавляют проверочный бит, который располагается в 8-й позиции. Элементы передаваемого блока и проверочные биты образуют матрицу:
а11 |
а12 |
а13 |
. . . а1n |
r1 |
|
а21 |
а22 |
а23 |
. . . |
а2n |
r2 |
. . . . . . . . . . . . . |
|||||
a71 |
a72 |
a73 |
. . . |
a7n |
r7 |
q1 |
q2 |
q3 |
. . . qn |
q(n+1), |
|
где аij (i=1, 2, . . .,7; j=1, 2, . . . , n) - информационные биты; q1, q2, q3, . . . , qn - проверочные биты знаков, образующие первую совокупность проверок. В конце матрицы стоят биты проверки на четность ri (i=1, 2, . . . , 7) которые являются суммой по модулю 2 всех элементов строки; r1 - r7 включается в знак проверки - это вторая совокупность проверок. К семи элементам знака добавляется восьмой проверочный бит q(n+1). Проверочные биты q1, q2, .
. ., q(n+1) формируются таким образом, чтобы число единиц в столбце было четным для асинхронных систем и нечетным - для синхронных. Каждый знак нужно передавать последовательно, начиная с первого бита aij и кончая восьмым проверочным.
Кодирующее устройство итеративного кода (рис. 21.5) содержит параллельный 8-раз- рядный сумматор по модулю 2 (D1), в котором формируется проверочный элемент столбца qj. Проверочный бит вместе с поступающей информационной кодовой комбинацией заносится в параллельно-последовательный регистр D3. Синхронизация записи осуществляется подачей управляющего импульса на вход С2. Сформированный байт подается на вход параллельно-последовательного сумматора по модулю 2 (D4), в котором осуществляется построчное суммирование передаваемых кодовых комбинаций. Операция суммирования в D4 синхронизируется импульсом, подаваемым на вход С в конце каждого восьмого такта. Поэлементная выдача байта данных в дискретный канал производится под действием сдвигающих тактовых импульсов, подаваемых на вход С1 и D3. Момент времени подачи ТИ и их количество определяются управляющим потенциалом, поступающим от устройства уп-
Глава 21. Устройства защиты от ошибок в передаваемой информации |
295 |
равления на вход схемы совпадения D2. В конце информационного блока контрольная сумма r1, r2, . . . , r7, q(n+1) переписывается в регистр сдвига D6 при наличии управляющего потенциала с УУ на втором входе D5 и выдается в последовательной форме на вход устройства преобразования сигналов (УПС).
В состав декодирующего устройства также входят сумматоры по модулю 2, осуществляющие проверку на четность поступающих байтов по столбцам и по строкам. Так как ошибка может быть обнаружена в любом столбце, то ее необходимо фиксировать в момент появления. Несоблюдение признака четности по строкам обнаруживается только по окончании блока.
Начальный знак блока НТ (начало текста) и символ СИН (синхронизация) не включают в суммирование. В блок включается комбинация КБ (конец блока), указывающая, что далее следует знак проверки матрицы.
a1 |
|
D3 |
|
D4 |
|
D6 |
|
D 0 |
RG Q 0 |
T M2 Q 0 |
D 0 |
RG |
|
||
a2 1 |
|
||||||
2 |
D 1 |
Q1 |
T |
|
|
|
|
a7 |
D 8 |
|
|
|
|
|
|
7 |
Q6 |
T |
Q6 |
D 6 |
|
|
|
|
D 7 |
|
|
||||
|
C2 |
Q7 |
T |
Q7 |
D 7 |
|
|
|
C1 |
Q8 |
C |
|
C |
Q7 |
|
|
D1 |
|
|
|
|||
|
M2 |
|
|
D5 |
|
|
|
|
q |
|
|
ТИ |
|
& |
На УПС |
|
|
|
& |
|
|||
ТИ |
|
|
|
|
|
D7 |
|
& |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D2
От УУ УЗО
Рис. 21.5. Кодирующее устройство итеративного кода
Кодовое расстояние итеративного кода d=4, он обнаруживает все ошибки кратности до трех и нечетной кратности, а также любой пакет ошибок длиной l+1, где l - длина строки матрицы кода. Недостатком итеративного кода, использующего проверку на четность по столбцам и строкам, является его высокая избыточность (≈ 15%). Однако кодирование и декодирование таких кодов очень просто реализуется программными методами, поэтому итеративные коды используются в аппаратуре передачи данных (АПД) с микропроцессорными УЗО. При более жестких требованиях по достоверности передачи данных применяют итеративный код с тремя проверками.
21.4. Корректирующий код Хэмминга
Код Хэмминга - один из наиболее эффективных кодов, позволяющих исправлять любую одиночную ошибку. Кодовое расстояние d=3. Код образуется путем дополнения информационной части передаваемого блока, состоящей из k бит, r проверочными элементами, причем в информационную часть при кодировании можно включать и служебные символы (номер, начало и конец блока), за исключением маркерных комбинаций, которые целесообразно располагать в начале блока. При выборе длины передаваемого блока n и количества проверочных элементов r следует руководствоваться неравенством 2r≥ n+1. Учитывая, что r=n-k, неравенство запишется в виде
Глава 21. Устройства защиты от ошибок в передаваемой информации |
296 |
2k<=2n/(n+1),
где n и k - целые числа. Неравенство является исходным для определения длины кодовой комбинации по заданному числу k. Из этих неравенств следует, например, что пять контрольных разрядов позволяют передавать в коде Хэмминга от 11 до 26 информационных разрядов и т.д.
Первый проверочный элемент П1 кода Хэмминга (КХ) образуется суммированием по модулю 2 всех нечетных бит блока, начиная с первого:
П1=а1+а3+а5+а7+ . . . .
Результат проверки П2 определяет второй разряд проверочной комбинации, называемой также синдромом ошибки. Он вычисляется суммированием тех бит блока, номера которых соответствуют n-разрядным двоичным числам, имеющим единицу во втором разряде, то есть
П2=а2+а3+а6+а7+а10+а11+ . . . .
Третья проверка П3 охватывает разряды, номера которых соответствуют n-разрядным числам, имеющим единицу в третьем разряде. Аналогично находятся разряды, охватываемые четвертой, пятой и т.д. проверками:
П3=а4+а5+а6+а7+а12+а13+а14+а15+ . . . ,
П4=а8+а9+а10+а11+а12+а13+а14+а15+ . . . ,
П5=а16+а17+а18+а19+а20+ . . . .
В таблице 21.2 показан пример построения КХ для семиразрядного слова.
Место расположения проверочных элементов не имеет значения, их можно размещать перед, после и чередуя с информационными символами. Если их расположить на местах, кратных степени 2, то есть на позициях 1, 2, 4, 8 и так далее, то код двоичного числа, образованного проверочными элементами, на приемной стороне будет указывать номер разряда, в котором произошла ошибка.
Таблица 21.2. Построение кода Хэмминга
_________________________________________________
Номер разрядов кодового слова Проверочные разряды
_________________________________________________
Десятичный Двоичный 1 2 3
_________________________________________________
1 |
0001 |
* |
|
|
2 |
0010 |
|
* |
|
3 |
0011 |
* |
* |
|
4 |
0100 |
|
|
* |
5 |
0101 |
* |
|
* |
6 |
0110 |
|
* |
* |
7 |
0111 |
* |
* |
* |
__________________________________________________
Контроль по КХ реализуется с помощью набора схем проверки на четность, которые при кодировании определяют контрольные разряды, а при декодировании формируют корректирующее число.
Поскольку основной операцией в кодирующих и декодирующих устройствах КХ является суммирование по модулю 2, то их схемы отличаются от схем кодеров итеративного кода образованием проверочных элементов. Для упрощения технической реализации (исключение многоразрядных параллельных сумматоров, входного накопительного регистра) вначале посылают в канал информационные биты, а затем проверочные. При таком способе формирование контрольных элементов можно осуществлять с помощью одноразрядных
