Материал: Телекоммуникационные системы и сети - КНИГА

Более эффективно используются дискретные каналы при приме­нении корректирующих кодов. В однонаправленных системах это должны быть коды, исправляющие ошибки. Широкое распростране­ние на практике получили двоичные корректирующие коды, т.е. коды, при формировании которых используются только два типа элементов: 0 и 1. Только такие коды и будут рассматриваться в данной главе.

Построение корректирующих кодов. Каждому символу исходно­го алфавита сообщений объема N_а поставим в соответствие n-элементную двоичную последовательность - кодовую комбинацию. Возможное (общее) число последовательностей длины n составляет N₀ = 2ⁿ, причем должно соблюдаться условие N₀ > N_а.

Если N₀ = N_а, то все возможные последовательности n-элементного кода используются для передачи или, как говорят, являются раз­решенными. Полученный таким образом код называется простым.

Пример 12.1. Для передачи сообщений, число которых равно восьми (N_а = 8), используется трехэлементный код. Число кодовых комбинаций, которое можно при этом получить, N₀ = 2³ = 8. Из табл. 12.1 видно, что комбинация под номером 0 отличается от комбинации 1 только в одной позиции. Следовательно, если при передаче комби­нации 000 произойдет ошибка в третьем элементе, то получим ком­бинацию 001.

Степень различия комбинаций определяется расстоянием Хемминга d. Это расстояние для любых двух кодовых комбинаций определя­ется числом несовпадающих в них разрядов. Например, две ниже на­писанные друг под другом комбинации не совпадают в двух разрядах:

поэтому расстояние Хемминга d = 2. Иначе его определяют как вес суммы по модулю два ( - условное обозначение суммы) этих кодо­вых комбинаций. Весом W кодовой комбинации называется число входящих в нее ненулевых элементов.

Таблица 12.1. Кодовые комбинации трехэлементного кода

Перебрав все возможные пары кодовых комбинаций, можно найти минимальное хеммингово расстояние, которое принято называть ко­довым и обозначать d₀. Для примера 12.1 кодовое расстояние d₀ = 1. Рассмотренный в примере код простой. Любая ошибка (даже одиноч­ная!) при использовании такого кода приведет к тому, что переданная разрешенная кодовая комбинация перейдет в другую разрешенную. Та­ким образом, простой код не способен обнаруживать и тем более ис­правлять ошибки и имеет d₀ = 1.

Для того чтобы код мог обнаруживать ошибки, необходимо, чтобы соблюдалось неравенство N_a < N₀. При этом неиспользуемые л-эле-ментные кодовые комбинации, число которых (N₀ - N_а), будем называть запрещенными. Они определяют избыточность кода. Очевидно, что появление ошибки в кодовой комбинации будет обнаружено, если пе­реданная разрешенная комбинация перейдет в одну из запрещенных. В качестве N_р = N_а разрешенных кодовых комбинаций надо выбирать такие, которые максимально отличаются друг от друга.

Пример 12.2. Алфавит передаваемых сообщений N_а = 2. Выберем из числа комбинаций, представленных в табл. 12.1, две. Очевидно, что ими должны быть комбинации 000, 111 или 001 и 110 и т.д. Кодо­вое расстояние d₀ = 3. Ошибки кратности один или два превращают любую разрешенную кодовую комбинацию в запрещенную. Следова­тельно, максимальная кратность обнаруживаемых таким образом ошибок равна двум (t_о.ош = 2).

Нетрудно догадаться, что минимальное кодовое расстояние d₀ и гарантированно обнаруживаемая кратность ошибок связаны соотно­шением t_о.ош = d₀ - 1.

Исправление ошибок возможно также только в том случае, если переданная разрешенная кодовая комбинация переходит в запре­щенную. Вывод о том, какая кодовая комбинация передавалась, де­лается на основании сравнения принятой запрещенной комбинации со всеми разрешенными. Принятая комбинация отождествляется с той из разрешенных, на которую она больше всего похожа, т.е. с той, от которой она отличается меньшим числом элементов. Так, если в примере 12.2 при передаче кодовой комбинации 000 получим 001, то вынесем решение, что передавалась кодовая комбинация 000.

Связь между d₀ и кратностью исправляемых ошибок определяется выражением t_и.ош = (d₀/2) - 1 для четного d₀ и t_и.ош = = (d₀ - 1)/2 для не­четного d₀.

Итак, задача получения кода с заданной корректирующей спо­собностью сводится к задаче выбора (путем перебора) из N₀ = 2ⁿ кодовых комбинаций N_а комбинаций с требуемым кодовым рас­стоянием d₀. Если л достаточно мало, то такой перебор не пред­ставляет особого труда. При больших n перебор может оказаться непосильным даже для современной ЭВМ, поэтому на практике используют методы построения кодов, не требующие перебора с целью получения кода с заданным d₀ и отличающиеся невысокой сложностью реализации.

Рис. 12.1. Классификация корректирующих кодов

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

Равномерные блочные коды делятся на разделимые и нераздели­мые. В разделимых кодах элементы разделяются на информацион­ные и проверочные, занимающие определенные места в кодовой комбинации, во-вторых, отсутствует деление элементов кодовых ком­бинаций на информационные и проверочные. К последним относится код с постоянным весом, например рекомендованный Международ­ным консультативным комитетом по телефонии и телеграфии (МККТТ), семиэлементный телеграфный код № 3 с весом каждой ко­довой комбинации, равным трем.

Примерами систематических кодов являются коды Хемминга и циклические. Последние реализуются наиболее просто, что и привело к их широкому использованию в УЗО. Для систематического кода применяется обозначение (n, k) - код, где n - число элементов в ком­бинации; k- число информационных элементов.

Характерной особенностью этих кодов является также и то, что ин­формационные и проверочные элементы связаны между собой зависи­мостями, описываемыми линейными уравнениями. Отсюда возникает и второе название систематических кодов - линейные.

Код Хемминга. Рассмотрим в качестве примера построение сис­тематического кода с кодовым расстоянием d₀ = 3 (кода Хемминга). Пусть число сообщений, которое необходимо передать, равно 16. То­гда необходимое число информационных элементов k= log₂N_a = 4. Можно выписать все 16 кодовых комбинаций, включая нулевую (0000). Это один из возможных способов задания исходного (просто­го) кода. Другой способ заключается в выписывании только четырех кодовых комбинаций простого кода в виде матрицы, называемой еди­ничной:

(12.1)

Суммируя по модулю два в различном сочетании кодовые комби­нации, входящие в единичную матрицу, можно получить 15 кодовых комбинаций, 16-я - нулевая. Кодовые комбинации, составляющие матрицу (12.1), линейно независимы. Можно было бы составить мат­рицу и из других кодовых комбинаций (лишь бы они были линейно независимыми). Ненулевые комбинации A₁, A₂, A₃, A₄ линейно неза­висимые, если , где при усло­вии, что хотя бы один из коэффициентов . Дополним каждую ко­довую комбинацию в (12.1) проверочными элементами так, чтобы обеспечивалось d₀ = 3. Будем иметь в виду также тот факт, что к чис­лу разрешенных комбинаций корректирующего кода принадлежит и комбинация 0000 ... 0, называемая нулевой. Очевидно, что в числе добавляемых проверочных элементов должно быть не менее двух единиц. Тогда общее число единиц в каждой комбинации кода полу­чим не меньше трех и комбинации, полученные нами, будут отличать­ся от нулевой, по крайней мере, в трех элементах. Добавим по две единицы к каждой строке матрицы (12.1):

. (12.2)

Складывая строки 1 и 2 матрицы (12.2) по модулю два

видим, что они отличаются только в двух элементах, т.е. заданное ко­довое расстояние не обеспечивается. Дополним каждую строку прове­рочными элементами так, чтобы d₀ = 3. Тогда матрица примет вид

. (12.3)

Добавляемые проверочные элементы могут быть записаны и в дру­гом порядке. Необходимо лишь обеспечить d₀ = 3.

Матрицу (12.3) называют производящей, или порождающей, мат­рицей кода (7,4), содержащего семь элементов, из которых четыре информационных. Обычно матрицу обозначают буквой G с индексом, указывающим, к какому коду она относится (в нашем случае G_(7,4)). Производящая матрица состоит из двух матриц - единичной (размер­ности k x k) и С_(r,k), содержащей r столбцов и k строк. Суммируя в различном сочетании строки матрицы (12.3), получаем все (кроме ну­левой) комбинации корректирующего кода с d₀ = 3.

Обозначим элементы комбинации полученного семиэлементного кода а₁, а₂, а₃, а₄, а₅, а₆, а₇, из которых а₁, а₂, а₃, а₄ - информационные и а₅, а₆, а₇ - проверочные. Последние могут быть получены путем суммирования по модулю два определенных информационных элемен­тов. Разумеется, правило формирования проверочного элемента а_i для любой кодовой комбинации одинаково.

Найдем правило формирования элемента а₅, пользуясь матри­цей (12.3). Из первой строки следует, что в суммировании должен обязательно участвовать элемент а₁ (только в этом случае а₅ = 1), из второй - что элемент а₃ в суммировании не должен участвовать, а из четвертой - что элемент а₄ должен участвовать в суммирова­нии. Итак,

. (12.4)

Уравнения для а₆ и а₇ по аналогии записываются в виде:

, (12.5)

(12.6)