Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема №5. КОДИРОВАНИЕ В ЦСПИ
Большинство современных систем связи используют различные методы кодирования. Кодирование наиболее часто применяется для борьбы с ошибками, возникающими при передаче сообщений по каналам связи, т. е. для повышения помехоустойчивости систем связи. Кроме того, кодирование позволяет получить идейно новые решения многих задач, возникающих при передаче информации. Так, с помощью кодирования устраняют негативные последствия глубоких замираний сигнала и многолучевого распространения, а также повышают эффективность ЦСПИ за счет устранения значительной избыточности реальных сообщений.
Прежде чем перейти непосредственно к помехоустойчивому кодированию рассмотрим основные понятия кодирования дискретных сообщений и первичное кодирование различными кодами.
5.1. Кодирование и декодирование дискретных сообщений
Для передачи по каналу связи любое сообщение должно быть преобразовано в первичный электрический сигнал. Между сообщением и сигналом должно быть однозначное соответствие, чтобы при обратном преобразовании на приемной стороне можно было получить переданное сообщение.
Первичные электрические сигналы, соответствующие дискретным сообщениям, называют цифровыми (дискретными). Систему соответствия символов дискретного сообщения и комбинаций элементов первичного цифрового сигнала называют кодом. Процесс преобразования символов дискретных сообщений в комбинации первичного цифрового сигнала определяют как кодирование. При кодировании каждому возможному символу сообщения из некоторого, заранее известного, множества однозначно определяется кодовая комбинация единичных элементов цифрового сигнала (например, «0» и «1»).
Процесс воспроизведения при приеме символов сообщения по принятым комбинациям элементов цифрового сигнала называется декодированием. Очевидно, что для реализации процедуры декодирования на приемной стороне получателю сообщения должен быть точно известен код, который использовался в процессе кодирования сообщения на передающей стороне. Т. е. между процедурами кодирования и декодирования должно быть однозначное соответствие, устанавливаемое используемым кодом.
Кодирование и декодирование дискретных сообщений в зависимости от вида и назначения используемого кода могут выполнять различные функции.
При выдаче сообщения от источника желательно привести объем содержащейся в нем информации в соответствие с пропускной способностью канала связи. В данном случае имеет место кодирование источника сообщения. При передаче сообщения по каналу связи необходимо обеспечить максимальную достоверность его приема на фоне имеющих место в канале помех и искажений сигнала, т. е. надо максимально адаптировать передачу под особенности канала связи. В этом случае реализуется кодирование канала.
Ниже будет показано, что кодирование источника и кодирование канала во многом соответствуют первичному и помехоустойчивому кодированию.
5.2. Кодирование канала и кодирование источника
На рис. 5.1 представлена структурная схема системы передачи информации. Источник выдает последовательность знаков дискретного сообщения, которая должна быть передана получателю по каналу связи. Знаками сообщения могут быть, например, буквы русского алфавита, двоичные символы и т. п.
Как уже отмечалось выше кодер, в данном случае, должен выполнять две основные функции: кодирование источника и кодирование канала, т. е. он должен состоять из кодера источника и кодера канала.
Кодер источника – осуществляет кодирование знаков дискретного сообщения (представляет их в виде кодовых комбинаций) и преобразует кодовые комбинации в первичный электрический сигнал (например, в последовательность импульсов постоянного тока, соответствующих передаче символов «0» и «1»). Задачей кодера источника является: во-первых, представить символы сообщения в виде кодовых комбинаций удобных для приведения к сигнальному виду; во-вторых, сокращение избыточности сообщений. Здесь в первом случае реализуется так называемое первичное кодирование, принципы которого боле детально будут рассмотрены ниже, а во втором - экономное кодирование.
Экономное кодирование позволяет сократить информационную избыточность передаваемых сообщений (сжать данные). Такой метод кодирования учитывает статистические характеристики источника сообщений и дает возможность представить знаки сообщения в среднем меньшим числом кодовых символов. Например, значительно сократить избыточность передаваемых сообщений можно, если наиболее часто встречающимся символам сообщений ставить в соответствие более короткие кодовые комбинации, а менее вероятным символам – более длинные. Экономное кодирование широко используется в ЦСПИ для сжатия речевых, факсимильных и телевизионных сообщений, которые обладают большой информационной избыточностью. Экономное кодирование часто называют также кодированием источника.
Кодер канала – добавляет в первичный цифровой сигнал, получаемый с выхода кодера источника, дополнительную (избыточную) информацию, предназначенную для защиты от ошибок передаваемого по каналу связи сигнала. Поскольку ошибки при приеме обычно являются следствием воздействия помех в канале связи, то реализуемое здесь канальное кодирование называют также помехоустойчивым кодированием. Данный вид кодирования будет детально рассмотрен ниже.
В соответствии с решаемыми задачами можно выделить три основных типа кодирования используемых в современных ЦСПИ: первичное, экономное и помехоустойчивое (рис.5.2).
Наиболее значимыми с точки зрения качества передачи информации для ЦСПИ являются первичное и помехоустойчивое кодирование.
5.3. Первичное и помехоустойчивое кодирование
Первичное кодирование позволяет представить множество дискретных величин кодовыми комбинациями. Например, для передачи по каналу связи текста на русском языке 32 буквы русского алфавита преобразуются в двоичные числа. В рассматриваемом случае каждой букве можно поставить в соответствие пятизначное двоичное число (количество различных пятизначных двоичных чисел равно N=25=32). Если все возможные кодовые комбинации используются для передачи сообщений, то код называется безызбыточным или первичным. Примерами таких кодов являются международный телеграфный код МТК-2, коды обмена информацией КОИ-7, КОИ-8 и др. Первичные коды обычно представляют в виде таблиц.
Некоторые, из наиболее часто применяемых, первичных кодов можно описать следующим образом.
Первичные коды
Код Морзе
Код Морзе является неравномерным первичным кодом. Характерной особенностью неравномерных кодов является различие между кодовыми комбинациями не только взаимным расположением элементов, но и их количеством.
Применение неравномерных кодов позволяет в принципе учесть статистику сообщений и обеспечить разновидность эффективного кодирования, т.е. часто встречающиеся в тексте знаки кодируются короткими комбинациями, а редко встречающиеся - длинными.
Первичный код МТК-2
Пятибитный код МТК-2 позволяет образовывать N = 25 = 32 кодовых комбинаций. Для передачи букв, цифр и знаков препинания этого количества кодовых комбинаций недостаточно. Поэтому код является трехрегистровым. Это означает, что каждой кодовой комбинации соответствует три знака из таблиц, соответствующих русскому, латинскому и цифровому тексту. Так, например, для передачи цифрового текста, после буквенного, необходимо нажать клавишу «Циф».
Использование рассматриваемого кода в системах передачи данных практически не эффективно, так как отсутствуют функциональные символы «Квитанция», «Ждите», «Понял» и др. Однако, в ряде случаев вместо этих символов передаются комбинации, которые не встречаются в смысловом тексте. Например, для обозначения начала текста используется сочетание знаков ЗЦЗЦ.
С развитием информационных цифровых систем появилась необходимость в использовании строчных и прописных букв, в расширении числа математических, графических и специальных знаков. Это привело к существенному увеличению объема алфавита, который значительно превышает возможности пятибитного кода.
Первичный семибитный код КОИ-7
На смену коду МТК-2 был разработан и в настоящее время широко применяется при передаче данных семибитный международный код №5 (МТК-5). На его основе в 1974 г. разработан семибитный код КОИ-7. Он состоит из 3-х таблиц:
кодовой таблицы КОИ-7 Н0;
кодовой таблицы КОИ-7 Н1;
кодовой таблицы КОИ-7 С1.
Кодовые комбинации кода обычно сопровождаются восьмым проверочным битом, который используется для обнаружения ошибок в кодовых комбинациях. Этот код используется в аппаратуре передачи данных, в том числе аппаратуре ЕС ЭВМ.
Недостаток кода КОИ-7 состоит в том, что он является регистровым, т.е. все три таблицы выбираются с помощью символов «ВХ» (выбор КОИ-7 Н0), «ВЫХ» (КОИ-7 Н1), «АР2» (КОИ-7 С1). Это приводит к снижению помехоустойчивости. Поэтому были разработаны безрегистровые первичные восьмиэлементные коды для передачи данных и их обработки - КОИ-8 и ДКОИ (двоичный код обмена данными). Оба кода содержат один и тот же набор символов, но различаются расположением в кодовых таблицах размерностью 16 строк на 16 столбцов (всего 256 кодовых позиций).
Помехоустойчивое кодирование позволяет обнаруживать и исправлять ошибки, возникающие при передаче сообщений по каналу связи. Помехоустойчивое кодирование осуществляется за счет введения в состав передаваемых кодовых символов достаточно большого объема избыточной информации (например, проверочных символов). Операцию введения избыточности для повышения помехоустойчивости канала связи называют канальным кодированием. Помехоустойчивое (канальное) кодирование находит широкое применение в ЦСПИ, в ЭВМ, в цифровой аудио- и видеотехнике.
Применение помехоустойчивых кодов является эффективным методом борьбы с помехами при приеме цифровых сигналов, позволяющим обнаруживать и исправлять ошибки в принятых кодовых комбинациях. Ошибка при приеме одной кодовой комбинации состоит в том, что, например, вследствие действия помехи в решающем устройстве приемника «0» заменяется «1» или, наоборот, «1» – «0». Если в кодовой комбинации лишь один символ заменяется ошибочным, то такую ошибку называют одиночной, если два – двойной и т. д.
В соответствии с теоремой К.Э.Шеннона для канала с помехами справедливо утверждение: если скорость передачи информации меньше пропускной способности канала (т. е. максимально возможной скорости передачи в данном канале), то существует метод кодирования, позволяющий получить сколь угодно малую вероятность ошибки на символ передаваемого сообщения. В данном случае имеется в виду не эффективное кодирование (как для канала без помех), а помехоустойчивое кодирование, задачей которого является обнаружение и исправление ошибок в принятых кодовых комбинациях. Таким образом, вторая теорема К.Э.Шеннона является принципиальным условием помехоустойчивого кодирования.
Для пояснения принципа помехоустойчивого кодирования рассмотрим два случая.
Случай 1. Пусть имеется куб (рис.5.3, а), вершины которого соответствуют некоторому алфавиту передаваемых сообщений (числу кодовых комбинаций). Предположим, передается кодовая комбинация (КК) «000», а в результате большого уровня помех в канале принимается «010». Так как все КК соответствует конкретному сообщению, то декодер, совершенно «не задумываясь» выдаст сообщение, соответствующее КК «010». Но на самом деле оно ошибочно.
Случай 2. Рассмотрим тот же куб (рис. 5.3, б), но разрешенными признаем всего две КК - «000» и «111», т.е. только за ними будут закреплены сообщения. Остальные КК, соответствующие вершинам куба для декодера определим запрещенными. Это означает, что за ними не закрепляются сообщения и в случае, если декодер на приемной стороне их примет, он «должен их признать» ошибочными, т.е. ошибка, имеющая место в первом случае обнаружится. Как видно из рисунка, ошибочный прием возможен только в ситуации, когда ошибочными будут все три разряда.
Рассмотренные случаи показывают следующую принципиальную основу помехоустойчивого кодирования: ошибки, возникающие в канале связи можно обнаруживать (и даже исправлять, что будет показано в дальнейшем) если код обладает избыточностью, т. е. он имеет запрещенные кодовые комбинации.
В помехоустойчивом коде: n - число элементов в кодовой комбинации; k – число элементов называемых информационными; - число проверочных элементов. Кодер при этом определяется как устройство ввода избыточности в первичный цифровой сигнал, а декодер как устройство, осуществляющее обнаружение и исправление ошибок в принятом кодовом слове. Кратность ошибки при помехоустойчивом кодировании это число искаженных символов в кодовом слове.
Таким образом, при использовании в системе связи помехоустойчивых кодов каждая кодовая комбинация должна сравниваться в приемнике со всеми разрешенными комбинациями кода. Если принятая комбинация совпадает с какой-либо разрешенной комбинацией, то она считается принятой верно и по ней восстанавливается сообщение, которое и считается переданным. Если же принятая комбинация не совпадает ни с одной разрешенной, то среди разрешенных комбинаций отыскивается наиболее близкая к принятой; она принимается в качестве переданной и по ней восстанавливается сообщение. Последовательность действий, обеспечивающая выбор одного из разрешенных сообщений по принятой комбинации, называется декодированием.
Следует отметить, что с увеличением длины кодовых комбинаций n число операций при декодировании резко возрастает. Именно поэтому были разработаны и разрабатываются специальные коды, которые позволяют осуществить декодирование более просто.
Помехоустойчивое кодирование занимает особое место среди методов кодирования используемых в ЦСПИ. Именно от эффективности помехоустойчивого кодирования главным образом зависит качество передачи информации представляемой в цифровом виде.
Рассмотренный на предшествующей лекции принцип помехоустойчивого кодирования на практике реализуются при построении различных по своей структуре и возможностям помехоустойчивых кодов. Однако, при всем многообразии таких кодов неизбежны общие черты свойственные основным их группам. С учетом данного обстоятельства целесообразно более детально рассмотреть вопрос классификации помехоустойчивых кодов и их характеристики, поскольку при этом появится возможность некоторой систематизации знаний в вопросе помехоустойчивого кодирования в целом.
5.4. Методы помехоустойчивого кодирования и классификация
помехоустойчивых кодов
В настоящее время разработано большое число методов помехоустойчивого кодирования. Соответственно помехоустойчивые коды могут быть классифицированы по различным признакам свойственным данным методам. Классификация помехоустойчивых кодов по некоторым признакам приведена на рис.5.4.
По способу метода кодирования помехоустойчивые коды обычно разбивают на два класса: блочные и непрерывные.
Блочное кодирование состоит в том, что последовательность символов источника сообщений (последовательность нулей и единиц) разделяется на блоки1, которые обычно называют кодовыми комбинациями. Блоки, содержащие k символов каждый, по определенному закону преобразуются кодером в n-символьные блоки, причем . В качестве примера на рис.5.5 представлена схема блочного кодера для и . Каждый символ выходного блока информации получается как сумма по модулю 2 нескольких символов входного блока, для чего используются n сумматоров по модулю 2.
Совокупность всех возможных кодовых комбинаций при блочном способе кодирования, и есть блочный код.
Блочные коды подразделяются на разделимые и неразделимые. К разделимым относятся коды, кодовые комбинации которых состоят из двух частей: информационной и проверочной. Обычно проверочные символы получаются посредством некоторых операций над информационными символами. Разделимые коды условно обозначают в виде (n, k), где n – число символов в кодовой комбинации, k – число информационных символов. Тогда число проверочных символов в разделимых блочных кодах равно r = n - r.
К неразделимым относятся коды, кодовые комбинации которых нельзя разделить на информационные и проверочные части. Примером неразделимого кода может служить код с постоянным весом.
Самый большой класс разделимых кодов составляют систематические коды, у которых значения проверочных символов определяются в результате проведения линейных операций над информационными символами. Последовательность линейных операций и число проверочных символов определяется тем, сколько ошибок должен исправлять и обнаруживать данный код. Проверочные символы могут располагаться на любом месте кодовой комбинации. Однако обычно проверочные символы дописывают к информационным символам справа, т. е. располагают на месте младших разрядов.
Пример простейшего кодера (5,4) для формирования систематического кода приведен на рис.5.6. Здесь всего лишь один проверочный символ формируется из информационных символов путем их суммирования по модулю 2. Этот код называют кодом с проверкой на четность. Так как новую разрешенную комбинацию систематического кода можно получить линейными преобразованиями двух разрешенных, то такие коды часто называют также линейными или групповыми.
К несистематическим (нелинейным) относятся коды, в которых проверочные символы формируются за счет некоторых нелинейных операций над информационными символами. Примером нелинейного кода является код Бергера.
Непрерывные коды характеризуются тем, что кодирование и декодирование информационной последовательности символов осуществляется без ее разбиения на блоки. Каждый символ выходной последовательности получается как результат некоторых операций над символами входной последовательности. Кодирование и декодирование непрерывных кодов носит непрерывный характер. При этом результат декодирования предыдущих или последующих символов может повлиять на декодирование текущего символа. Среди непрерывных кодов наиболее часто применяют сверточные коды.
Примеры простейших помехоустойчивых кодов и их корректирующие возможности будут приведены ниже.
5.5. Основные характеристики помехоустойчивых кодов
Основными характеристиками помехоустойчивых кодов являются: длина кода n, его основание m, общее число кодовых комбинаций N, число разрешенных кодовых комбинаций Nр, избыточность кода Ки и минимальное кодовое расстояние dmin.
Длина кода2 n – это число символов в кодовой комбинации. Например, комбинация 11010 состоит из пяти символов, следовательно, n=5. Если все кодовые комбинации содержат одинаковое число символов, то код называется равномерным. В неравномерных кодах длина кодовых комбинаций может быть разной.
Основание кода m – это число различных символов в коде. Для двоичных кодов символами являются 1 и 0, поэтому m=2.
Число кодовых комбинаций для равномерного кода равно N=mn. Например, для равномерного двоичного кода, имеющего длину n=6, число различных кодовых комбинаций равно N=26=64.
Число разрешенных кодовых комбинаций Nр – это количество кодовых комбинаций кода, используемых для передачи сообщений. Для помехоустойчивых кодов Nр<N. Оставшиеся кодовые комбинации N-Nр называют запрещенными. Если Nр=N, то код является безызбыточным. Для разделимых кодов Nр=2 k.
Избыточность кода Ки в общем случае определяется выражением
. (5.1)
и показывает, какая доля длины кодовой комбинации не используется для передачи информации, а используется для повышения помехоустойчивости кода. Для разделимых кодов
, (5.2)
где величина k/n называется относительной скоростью кода.
Кодовое расстояние d(А,В) – это число позиций, в которых две кодовые комбинации А и В отличаются друг от друга. Например, если А=01101, В=10111,то d(А,В)=3. Кодовое расстояние между комбинациями А и В может быть найдено в результате сложения по модулю 2 одноименных разрядов комбинаций, а именно
, (5.3)
где ai и bi – i-е разряды кодовых комбинаций A и B; символ обозначает сложение по модулю 2. Например, чтобы получить кодовое расстояние между комбинациями 1101011 и 0111101 достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2:
Кодовое расстояние между различными комбинациями конкретного кода может быть различным. Так, для первичных кодов (приложения 1, 2) это расстояние для различных пар кодовых комбинаций может принимать значения от единицы до величины длины кода.
Минимальное кодовое расстояние dmin – это минимальное расстояние между разрешенными кодовыми комбинациями данного кода. Минимальное кодовое расстояние является основной характеристикой корректирующей способности кода. В первичных (безызбыточных) кодах все комбинации являются разрешенными, поэтому минимальное кодовое расстояние для них равно единице (dmin = 1). Такие коды не способны обнаруживать и исправлять ошибки. Для того чтобы код обладал корректирующими способностями, его минимальное кодовое расстояние должно быть не менее двух (dmin 2).
Для обнаружения всех ошибок кратностью3 s и менее, минимальное кодовое расстояние должно удовлетворять условию
dmin s +1 . (5.4)
Если код используется для исправления ошибок кратности не более t, то минимальное кодовое расстояние должно иметь значение
dmin 2t +1 . (5.5)
Например, из (5.4) и (5.5) следует, что для обнаружения однократных ошибок (s = 1) требуется код с dmin = 2, а для того чтобы исправить такие ошибки, требуется код с кодовым расстоянием dmin = 3.
Для обнаружения s ошибок и исправления t ошибок должно выполняться условие
dmin s + t +1 . (5.6)
Таким образом, задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния. Увеличение dmin приводит к росту избыточности кода. При этом желательно, чтобы число проверочных символов r было минимальным. В настоящее время известен ряд верхних и нижних границ, которые устанавливают связь между кодовым расстоянием и числом проверочных символов. Сведения о границах для кодового расстояния будут приведены позже в процессе оценки качества приема кодированных сообщений.
Код с постоянным весом. Одним из простейших блочных неразделимых кодов (см. рис.5.4) является код с постоянным весом. Примером такого кода может служить семибитный телеграфный код МТК-3, в котором каждая разрешенная кодовая комбинация содержит три единицы и четыре нуля (рис.5.7). Весом кодовой комбинации называют число содержащихся в ней единиц. В рассматриваемом коде вес кодовых комбинаций равен трем.
Число разрешенных кодовых комбинаций в кодах с постоянным весом определяется как количество сочетаний из n символов по g и равно
,
где n – длина кодовой комбинации, а g – вес разрешенной кодовой комбинации. Для кода МТК-3 число разрешенных кодовых комбинаций равно . Таким образом, из общего числа комбинаций N=27=128 только 35 используются для передачи сообщений.
Избыточность кода с постоянным весом МТК-3
.
Минимальное кодовое расстояние такого кода dmin=2, что дает ему возможность обнаруживать однократные ошибки. Однако код с постоянным весом способен обнаруживать ошибки большей кратности (двойные, тройные и т.д.), при которых нарушается весовое соотношение единиц и нулей. Код не обнаруживает только ошибки, при которых число единиц, перешедших в нули, равно числу нулей, перешедших в единицы.
Следует отметить, что в настоящее время предпочтение отдается разделимым кодам, так как они проще реализуются.
Код с проверкой на четность. Этот код является наиболее простым блочным разделимым кодом, содержащим всего лишь один проверочный символ. Проверочный символ выбирается равным единице или нулю, таким образом, чтобы число единиц во вновь образованной n=k+1 – элементной кодовой комбинации было четным (рис.5.8).
Код с проверкой на четность относится к классу линейных систематических кодов. Формирование проверочных символов кодовых комбинаций кода с четным числом единиц осуществляется путем сложения по модулю 2 информационных символов. Например, к первичной комбинации 01011 следует добавить справа единицу, так как 01011=1, следовательно, разрешенная кодовая комбинация запишется так: 010111 (см. также рис.5.6).
Код с проверкой на четность является линейным, поскольку поэлементное сложение по модулю 2 двух разрешенных кодовых комбинаций образует также разрешенную кодовую комбинацию. Действительно, сложив две кодовые комбинации, приведенные на рис.5.7, получим
Число разрешенных кодовых комбинаций равно:
,
т. е. из общего числа возможных комбинаций только половина используется для передачи сообщений.
Избыточность кода с проверкой на четность минимальна и равна
.
Для шестибитного кода (рис.5.8)
.
Минимальное кодовое расстояние кода с проверкой на четность равно двум (dmin=2). Легко убедиться, что проверка на четность позволяет выявить одиночную ошибку, поскольку она изменяет четность. Кроме однократных ошибок, этот код позволяет обнаруживать все ошибки нечетной кратности. Ошибки четной кратности код не обнаруживает. Например, если в кодовой комбинации будут искажены два символа, то четность не изменится и ошибка не будет обнаружена.
Код Бергера или код с контрольным суммированием является несистематическим кодом, у которого проверочные символы представляют собой двоичную запись числа единиц в последовательности информационных символов. Например, информационная последовательность 01011 содержит три единицы. Десятичному числу 3 соответствует двоичная запись 011, поэтому разрешенная кодовая комбинация кода Бергера примет вид: 01011011. Примеры разрешенных кодовых комбинаций данного кода приведены на рис.5.9, где проверочные символы обозначены затемнением.
Минимальное кодовое расстояние кода равно двум. Коды Бергера обнаруживают все одиночные ошибки и некоторую часть многократных ошибок. Эти коды обладают примерно такой же корректирующей способностью, что и код МТК-3, но имеют важное преимущество – они являются разделимыми, что упрощает реализацию кодирующих и декодирующих устройств.
Код с повторением является простейшим кодом, в котором информационные символы повторяются несколько раз. При этом может дублироваться -раз каждый символ или каждая информационная кодовая комбинация. Например, пятибитной информационной кодовой комбинации 11010 соответствует разрешенная комбинация кода с повторением при =2: 1111001100 или 1101011010. Таким образом, проверочными символами данного кода являются информационные символы. Код с повторением является разделимым систематическим кодом.
Основные характеристики кода зависят от числа повторений и равны:
, , .
Код с повторением способен не только обнаруживать ошибки, но и исправлять их. Однако для исправления даже одиночных ошибок требуется трехкратное повторение, т.е. трехкратное увеличение длины кода. Это слишком большая цена. Поэтому код с повторением хотя и применяется, но является низкоскоростным, поскольку имеет высокую избыточность. Например, при двукратном повторении минимальное кодовое расстояние равно двум (dmin=2), а избыточность Kи=0.5, которая существенно превышает избыточность, рассмотренных ранее кодов.
Код Бауэра (инверсный код). Этот код является разновидностью кода с двукратным повторением, обеспечивающим минимальное кодовое расстояние, равное четырем (dmin=4). При образовании данного кода, кодовые комбинации с четным числом единиц повторяются в неизменном виде (рис.5.10 а), а кодовые комбинации с нечетным числом единиц – в инвертированном (рис.5.10 б).
Код Бауэра называют также инверсным кодом. При небольших длинах кодовых комбинаций (n=10…14) инверсный код по своим корректирующим способностям не уступает более сложным кодам с такой же величиной избыточности.
Рекуррентный код (цепной код). Это непрерывный код, у которого проверочные символы чередуются с информационными по всей длине кодовой последовательности. Формирование проверочных символов в таких кодах осуществляется по рекуррентным правилам. В простейшем случае проверочные символы формируются путем суммирования по модулю 2 двух соседних информационных символов
, (5.7)
где bi – i-й проверочный символ; ai – i-й информационный символ, принимающий значение 0 или 1. Далее проверочные символы, сформированные по правилу (7), перемежаются с информационными, образуя непрерывную последовательность (рис.5.11).
Цепной код позволяет установить, какой из символов был искажен: информационный или проверочный. При приеме сравнивают принятые проверочные элементы с вычисленными , т.е. проверяют выполнение условия
. (5.8)
Искажение одного информационного символа ai приводит к невыполнению (5.8) для двух символов: и . Таким образом, если условие (5.8) не выполняется для двух соседних проверочных элементов, то искаженным элементом является информационный элемент, находящийся между ними. Это означает, что его следует изменить на противоположный.
Рис.5.9. Примеры разрешенных кодовых комбинаций кода Бергера
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
Рис.5.10. Примеры разрешенных кодовых комбинаций кода Бауэра
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
а)
б)
1 На практике количество символов в блоке может лежать в пределах от трех до нескольких сотен.
2 Под длиной кода также понимают количество знаков кодовой комбинации или разрядность кода.
3 Напомним, что кратность ошибки – это число позиций кодовой комбинации, в которых под воздействием помех одни символы оказались замененными другими (нули – единицами, единицы - нулями).