Пенин П.И. Системы передачи цифровой информации (1976) (1151855), страница 58
Текст из файла (страница 58)
Итак, применяя для передачи цифровой информации код, у которого используются не все возможные комбинации, а только некоторые из них, можно повысить помехоустойчивость приема. Такие коды называют избыточными, или корректирующими. Корректирующие свойства избыточных кодов зависят от правила построения этих кодов, определяющего их структуру, и параметров кода !длительности символов, числа разрядов, избыточности и т. п.). Простейшим примером корректирующего кода является код с проверкой на четность.
Такой код строят следующим образом. К кодовым комбинациям безызбыточного первичного двоичного А-разрядного кода добавляется дополнительный разряд !позиция), называемый проверочным, или контрольным. Если число символов 1 в исходной кодовой комбинации четное, то в дополнительном разряде формируют контрольный символ О, если число символов 1 нечетное, то в дополнительном разряде формируют контрольный символ 1. В результате общее число символов 1 в любой кодовой комбинации всегда должно быть четным. Нетрудно видеть, что добавление дополнительного разряда увеличило общее число возможных комбинаций вдвое по сравнению с числом комбинаций исходного первичного кода, а условие четкости разделило все комбинации на разрешенные и неразрешенные. Код с проверкой на четность позволяет обнаруживать одиночную ошибку при приеме кодовой комбинации, так как такая ошибка нарушает условие четности, т.
е. переводит разрешенную комбинацию в неразрешенную. Увеличивая число дополнительных разрядов и фор. мируя по определенным правилам проверочные символы О нлн 1, соответствующие этим разрядам, можно зоз усилить корректирующие свойства кода так, чтобы код позволял не только обнаруживать, но и исправлять ошибки. В связи с этим избыточные или корректирующие коды иногда разделяют па коды, обнаруживающие ошибки, и коды, исправляющие ошибки. Для обнаруже.
ния ошибки достаточно установить факт, что в данной кодовой комбинапии произошла ошибка (одиночная, двойная и т. п.). Для исправления ошибки необходимо не только обнаружить ошибку, но н указать ту позицию в кодовой комбинации, где эта ошибка произошла. Естественно, что такая задача значительно сложнее, чем обнаружение ошибки, и требует применения более сложных кодов. 8.8.1. Основные виды корректирующих кодов Исследованию корректирующих кодов посвящено огромное количество работ, начиная от сугубо математических и кончая отдельными частными работами прикладного характера. Поэтому в этой области, более чем в любой другой, существует множество различных терминов, часто выражающих одно и то же понятие. Известно большое число кодов, названных по фамилиям авторов, впервые предложивших эти коды.
Все это затрудняет пользование литературой по вопросам кодирования, особенно для читателей, начинающих впервые знакомиться с этой обширной областью. Наиболее систематично вопросы кодирования изложены в работах (11, 20 — 241. В настоящее время наибольшее внимание с точки зрения технических приложений уделяется двоичным равномерным корректирукмцим кодам, так как они обладают хорошими корректирующими свойствами и их реализация сравнительно проста.
Двоичные равномерные коды делятся на блочные и непрерывные. Остановимся кратко на рассмотрении некоторых особенностей этих классов кодов. Блочные коды. При использовании блочных ходов цифровая информация передается в виде отдельных кодовых комбинаций (блоков) равной длины. Кодирование и декодирование каждого блока осуществляется независимо друг от друга. Почти все блочные коды относятся к разделимым кодам, т. е, таким, кодовые комбинации которых состоят 309 из двух различающихся частей: информационной и про-. верочной. Информационные н проверочные разряды во всех кодовых комбинациях разделимого кода всегда занимают одни и те же позиции.
Разделимые коды обычно условно обозначают в виде (и, А), где л указывает общую значность кода 1общее число позиции в блоке), й — число информационных позиций. Иными словами, величина п определяет общее число символов в блоке, а й — только число информационных символов '. Таким образом, число проверочных символов в разделимых кодах равно ге и — Й. Среди разделимых кодов различают систематические и несистематические коды.
Систематические, нли линейные коды образуют наиболее обширную группу разделимых кодов. Особенностью систематических кодов является то, что проверочные символы образуются различными линейными комбинациями информационных символов. Теоретической основой получения таких комбинаций является аппарат линейной алгебры, который позволяет формировать проверочные символы по вполне определенным правилам (по определенной системе — отсюда и происхождение термина «систематические» коды). Использование аппарата линейной алгебры, в которой очень важное значение имеет понятие «группа», привело к тому, что в ряде работ рассматриваемые коды называют также «алгебраическими» или «групповыми» 120, 24).
Систематические коды обстоятельно изучены. Наиболее известны среди них циклические коды. Важными представителями циклических кодов являются коды Хэмминга, которые исторически появились раньше многих других кодов и сыграли большую роль в развитии теории корректирующих кодов, а также коды Боуза— Чоудхури. Для таких кодов найдены сравнительно простые методы их реализации. Исследования показали, что эти коды имеют особенно важное значение для приложений.
Основное свойство циклических кодов состоит в том, что циклический сдвиг любой разрешенной кодо- * заметим, что здесь мы отступили от обозначений, использованных в предыдущих главах 1т-»вечность кода, л — основание кода). Дело в том, что обозначение разделимого кода в виде (л, й) широко распространено в литературе н мы его сохранили в привычной аапнси. 310 йои кьмбина11нн Факже являешься разрешенной комбинацией. Циклические коды обладают хорошими корректирующими свойствами, а реализация коднрующих и декодирующих устройств для таких кодов оказывается проще, чем для других систематических кодов. Непрерывные коды.
Такие коды характеризуются тем, что в них проверочные символы перемежаются с информационными, и нет четкого деления получающейся на выходе кодирующего устройства последовательности символов на отдельные кодовые комбинации. Формирование проверочных символов в непрерывных кодах ведется по рекуррентным правилам, поэтому непрерывные коды часто называют цепными, или рекуррентнымн.
Исследованию непрерывных кодов уделяется большое внимание, поскольку кодирование и декодирование таких кодов несколько проще, чем систематических. Важно отметить, что непрерывные коды могут иметь хорошие корректирующие свойства, особенно для ошибок, возникающих «пачками» [11, 2О, 24). Проблема помехоустойчнвого кодирования представляет собой обширную область теоретических и прикладных исследований. Ее основными задачами являются: 1) отыскание кодов, эффективно исправляющих ошибки требуемого вида; 2) нахождение методов кодирования и способов их реализации; 3) нахождение методов декодирования и приемлемых способов их реализации.
Наиболее разработаны эти задачи применительно к систематическим кодам. Такие коды успешно применяются в вычислительной технике и различных автоматизированных цифровых устройствах. Некоторые из предложенных кодов оказались удобными и для применения в цифровых системах передачи информации. В следующих трех параграфах кратко излагаются .некоторые особенности систематических корректирующих кодов, методы их кодирования и декодирования, а также рессматриваются возможности применения та.ких кодов для повышения помехоустойчивости приема. В.В.2.
Основные параметры корректирующих кодов Основными параметрами, характеризующими кор- ;ректирующие свойства кодов являются избыточность 3!1 кода, кодовое расстояние, число обнаруживаемых или исправляемых ошибок. Рассмотрим суть этих параметров. Избыточность корректирующего кода. Избыточностью корректирующего кода называют велнчину в г/л (л — й)/п 1 — й/и. (6.57) Из (6.57) следует (6.58) Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют информационные символы.
В теории кодирования величину л/я принято называть скоростью передачи (1Ц. Необходимо иметь в виду, что величина л/л характеризует относительную скорость передачи информации. Если производительность источника информации равна Н символов в секунду, то скорость передачи после кодирования этой информации окажется равной Я=Нй/л, (6.59) поскольку в закодированной последовательности из каждых п символов только Й символов являются информационными.
Если число ошибок, которые нужно обнаружить или исправить, значительно, необходимо иметь код с большим числом проверочных символов. Чтобы при этом скорость передачи оставалась достаточно высокой, необходимо в каждом кодовом блоке одновременно увеличивать как общее число символов, так и число информационных символов. При этом длительность кодовых блоков будет существенно возрастать, что приведет к задержке'информации при передаче и приеме. Чем сложнее кодирование, тем длительнее временная задержка информации.
Кодовое расстояние. При изучении корректирующих кодов очень полезно понятие о кодовом расстоянии или расстоянии Хэмминга. Расстоянием и' между двумя кодовыми комбинациями называют число позиций, в которых эти комбинации имеют разные символы. Например, расстояние между комбинациями 0001101 и 1001010 равно четырем (и'=4). Расстояние между различными комбинациями некоторого конкретного кода может быть различным. Так, в частности, в безызбыточном первичном натуральном коде это расстояние для различных 312 комбинаций может различаться от единицы до величины пз, равной значности исода. Особую важность для характеристики корректирующих свойств кода имеет минимальное расстояние 4~, между кодовыми комбинациями.
Это растояние называют кодовым, илн хэммннговым. В безызбыточном коде все комбинации являются разрешенными и, следовательно, его кодовое расстояние равно единице. Поэтому достаточно исказиться одному символу, чтобы вместо переданной комбинации была принята другая разрешенная комбинация. Чтобы код обладал корректирующими свойствами, необходимо ввести в него некоторую избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух. Число обнаруживаемых или исправляемых ошибок.
Кодовое расстояние является основным параметром, характеризующим корректирующие способности данного кода. Если код используется только для обнаружения ошибок кратностью а, то необходимо и достаточно, чтобы минимальное расстояние было равно * 4,ш~)а+1. (6.60) В этом случае никакая комбинация из а ошибок не может перевести одну разрешенную кодовую комбинацию в другую разрешенную. Таким образом, условие обнаружения всех ошибок кратностью а можно записать в виде аоб (С( — 1.
(6.61) Чтобы можно было исправить все ошибки кратностью а и менее, необходимо иметь минимальное расстояние, удовлетворяющее условию с(,нп»2а+1. (6.62) В этом случае любая кодовая комбинация с числом ошибок а отличается от каждой разрешенной комбинации не менее чем в а+1 позициях. Если условие (6.62) не выполнено, возможен случай, когда ошибка кратности а исказит переданную комбинацию так, что она станет ближе к одной из разрешенных комбинаций, чем к переданной, или даже перейдет в другую разрешен- е Кратностью ошибки а называют число позиций кодовой комбинации, ° которыл под действием помехи одни символы оказались замененными другими. Например, О на 1 или 1 иа О. 313 ную комбинацию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
