2.2.9. Пример задания по контрольной работе – часть 2

1. Определить объем используемого алфавита, если известно, что 10-значное сообщение, составленное из этого алфавита, несет в себе 20 бит информации.

2. Закодировать по методике Хаффмена следующие буквы первичного алфавита: ,,,,,. Вероятностьопределить.

3. Информационная избыточность сообщений, составленных из 8-буквенного алфавита, равна 0,3. Определить среднее количество информации, приходящееся на 1 знак такого сообщения.

4. Комбинация комбинированного инверсного кода имеет вид: 110111111111. Какое число передавалось?

5. Закодировать корреляционным кодом следующую комбинацию 11111001.

2.3. Контрольная работа – часть 3

В контрольную работу включены задачи из следующих разделов теории кодирования:

• Кодирование линейными кодами по заданной контрольной матрице;

• Матричный метод построения контрольной матрицы линейных кодов;

• Синдромный метод декодирования линейных кодов;

• Построение схем кодирования и декодирования линейных кодов;

• Формирование разрешенных комбинаций циклических кодов по заданному образующему многочлену;

• Декодирование циклических кодов;

• Построение схемы делителя на образующий многочлен на регистре сдвига с сумматорами по mod2.

Краткие теоретические сведения

2.3.1. Линейные коды, обнаруживающие и исправляющие ошибки

Линейными называют коды, в которых проверочные символы представляют собой линейные комбинации информационных символов, т.е. линейные коды являются систематическими.

Основой математического описания линейных кодов является теория алгебраических систем (теория групп, колец, матриц и т.д.).

Кодовые комбинации в линейных кодах рассматриваются как элементы множества.

Алгебраическими системами называют множества, для которых определены некоторые алгебраические операции. Под алгебраической операцией понимается однозначное сопоставление двум элементам третьего элемента по определенным правилам. Обычно такой операцией является сложение () или умножение ().

Рассмотрим кратко такие алгебраические системы, как группа и кольцо.

Группойназывается множество элементов (кодовых комбинаций), объединенных определенным законом композиции. Это значит, что задана некоторая операция, в результате применения которой к любым двум комбинациям группы образуется третья комбинация, также принадлежащая этой группе. Иными словами, группа – это множество кодовых слов, обладающих свойством замкнутости относительно операции.

Группа, состоящая из конечного числа элементов, называется конечной.

Чтобы множество n-разрядных кодовых комбинаций, было конечной группой, при выполнении основной операции число разрядов в результирующей комбинации не должно увеличиваться. Этому условию удовлетворяет операция символического поразрядного сложения по заданному модулю, при которой цифры одинаковых разрядов элементов группы (кодовых комбинаций) складываются обычным порядком, а результатом сложения считается остаток от деления полученного числа на модуль.

2.3.2. Построение двоичного линейного кода

Когда речь идет о линейных кодах, кодовые комбинации принято называть кодовыми векторами (КВ).

Линейный код обычно обозначают как , где– значность КВ,– число информационных символов. Следовательно, число проверочных (контрольных) символов.

Построение линейного начинается с выбора числа информационных разрядов в кодовых векторах. Это число выбирается, исходя из требуемого объема кода, т.е. максимального числа сообщений, которое требуется передавать.

В случае передачи двоичным кодом величина должна удовлетворять неравенству:

(2.9)

(единица вычитается из потому, что нулевая комбинация обычно не используется при передаче, т.к. не изменяет состояния канала).

После выбора определяется число контрольных разрядов, необходимое для получения требуемой корректирующей способности кода.

Если требуется исправлять все одиночные ошибки (кодовое расстояние кода ), величинавыбирается из следующих соображений. Под действием помех может быть искажен любой символ в n-значном КВ, т.е. для каждого кодового вектора возможноисходов передачи (учитывает правильную передачу). С помощью контрольных символов нужно различать все возможные исходы передачи. Это возможно, если выполняется условие:

, (2.10)

где – число сочетаний изпо 1.

Уравнение (2.10) является трансцендентным относительно , поэтому при небольшихвеличинуопределяют простым подбором, принимая минимальное значение, удовлетворяющие (2.10).

При больших для определенияприможно использовать эмпирическое соотношение:

, (2.11)

где – знак округления до ближайшего большего числа.

Если необходимо исправлять не только все единичные, но и все двойные независимые ошибки, величина должна выбираться в соответствии с условием:

(2.12)

После определения составляется образующая матрица, состоящая изстрок истолбцов. В общем виде образующая матрица имеет вид:

(2.13)

Кодовые векторы, входящие в образующую матрицу, являются исходными разрешенными. Поскольку двоичный линейный код является групповым по сложению, остальные разрешенные КВ получаются путем суммирования по модулю 2 строк образующей матрицы сначала попарно, затем по три, наконец, всех -строк.

В качестве строк образующей матрицы могут быть взяты любые КВ, отвечающие следующим условиям. Они должны быть:

1. n-значными;

2. отстоящими друг от друга на заданное кодовое расстояние;

3. ненулевыми;

4. иметь вес не менее заданного кодового расстояния кода;

5. линейно-независимыми.

Последним шагом в построении линейного кода является составление проверочной (контрольной) матрицы, имеющей nстолбцов иmстрок. В общем виде контрольная матрица имеет вид:

(2.14)

Элементы , составляющие контрольную матрицу, представляют собой элементы КВ, ортогональных любым разрешенным кодовым векторам. Если обозначить черезV-разрешенные КВ данного линейного кода, а черезU-вектор контрольной матрицы, то условие ортогональности КВVиUв математической форме записывается так:

, (2.15)

где и,, – соответственно, элементы разрешенных КВ и векторов контрольной матрицы.

Кроме того, что любой вектор контрольной матрицы должен быть ортогонален любому разрешенному КВ, матрица в целом должна удовлетворять следующему требованию: в контрольной матрице не должно быть нулевых и одинаковых столбцов.

После построения контрольной матрицы линейный код является полностью определенным. На этапе кодирования КВ формируется так, чтобы он был ортогонален каждому из векторов контрольной матрицы, а на этапе декодирования принятый КВ, возможно содержащий ошибки, проверяется на ортогональность векторам матрицы H.

Пример

Построить линейный -код, позволяющий исправлять все одиночные ошибки, если требуемый объем кода.

Решение.

1. Определяем требуемое число информационных разрядов. Согласно (2.9) имеем: ,, откуда.

2. В соответствии с (2.11) определяем требуемое число контрольных разрядов:

,.

Следовательно, , а код имеет формат (7, 4).

3. Составляем образующую матрицу .

Так как линейный код должен исправлять однократные ошибки, то кодовое расстояние между комбинациями образующей матрицы должно удовлетворять условию (2.8): . Учитывая, что векторы образующей матрицы (2.13) являются разрешенными, в дальнейшем на основании условия ортогональности векторов V и U подбираются коэффициентытак, чтобы в контрольной матрице не было нулевых и одинаковых столбцов. В результате выполнения этих действий получена контрольная матрица (2.16). (При выполнении контрольной работы матрицаНбудет задана.)

(2.16)