3. Выбор корректирующего кода

Необходимость применения методов защиты устанавливается при сравнении значения Р_{ош к} с допустимым значением, указанным в задании (см. табл. 1). Если сравнение показывает, что значение Р_{ош к}, рассчитанное по формуле (8), менее допустимого, т. е. нет необходимости в дополнительных мерах повышения верности, то следует по графику Р_э = f() взять другое значение Р_э, при котором Р_{ош к} будет более допустимого. Изменение значения  означает предъявление приемнику более (большее ) или менее (меньшее ) жестких требований по исправляющей способности, что тоже можно расценивать как один из методов повышения верности передачи информации.

В современных технологиях передачи любого вида информации широко используются корректирующие (избыточные) коды как средство повышения верности. Для целей курсового проектирования этот метод анализируется на примере избыточного кодирования и декодирования одной кодовой комбинации простого (неизбыточного) кода в соответствии с заданием – кода МТК-2 или КОИ-7 с количеством разрядов пять или семь соответственно. В отличие от этого в реальных системах кодирование и декодирование чаще всего осуществляются по блокам (кадрам), которые составляют сотни и даже тысячи разрядов. Например, в технологии Х.25 передача ведется блоками переменной длины, в зависимости от качества канала – 16, 32, 64, 256, 512, 1024, 2048 и 4096 байт, т. е. максимальная длина блока составляет 32 768 разрядов.

Важным параметром корректирующего кода является минимальное кодовое (хэммингово) расстояние d₀, которое определяется как минимальное количество отличающихся разрядов при попарном сравнении всех разрешенных комбинаций кода. Для простых (некорректирующих) кодов d₀ = 1, для избыточных (корректирующих) d₀ ≥ 2.

Корректирующие коды могут использоваться в двух режимах – исправ-ления или обнаружения ошибок. Во втором режиме декодер приемного устройства формирует сигнал наличия ошибок, не определяя точно ошибочные разряды. Исправление при этом должно осуществляться другим методом, например, повторной передачей ошибочной комбинации (блока) в системах с решающей обратной связью (РОС).

Кратность гарантированно обнаруживаемых  и исправляемых t ошибок связана с минимальным кодовым расстоянием соотношениями: d₀ =  + 1; d₀ = 2t + 1.

Для определения значения  или t поочередно исключают из общей суммы вероятность однократной (Р₁), двукратной (Р₂), … ошибок, пока оставшаяся сумма не окажется меньше допустимого значения. Количество исключенных членов и означает необходимую кратность исправляемых (t) или обнаруживаемых () ошибок.

Одним из наиболее распространенных видов корректирующих кодов является циклический. Его название объясняется свойством получения ряда разрешенных комбинаций путем циклического сдвига одной исходной, например, из комбинации 10010110, если она является разрешенной, будут образованы другие разрешенные комбинации: 00101101, 01011010 и т. д. Этот код является разновидностью систематических блочных, он может быть разделимым и неразделимым. Преимуществами циклического кода по сравнению с другими систематическими кодами являются высокая корректирующая способность при сравнительно простых алгоритмах и схемах кодирования и декодирования и эффективность работы в условиях наличия коррелированных ошибок.

При построении циклических кодов кодовые комбинации принято представлять в виде полиномов:

P(x) = a_n-1 x^n-1 + a_n-2 x^n-2 + . . . + a₁ x¹ + a₀ x⁰, (9)

где a _n-1, ... , a₀ - коэффициенты, принимающие значения, равные нулю или единице;

х  основание кода, х = 2.

Например, комбинации 1011 соответствует многочлен P(x) = 1 x³ + 0x² + +1x +1x⁰ = x³ + x + 1.

Циклическими (n, k)-кодами называются коды, каждая кодовая комбинация которых, выраженная в виде полинома, имеет степень, не превышающую n  1, и нацело делится на некоторый полином g(x) степени r. Полином g(x) называется образующим (производящим, порождающим), от его выбора зависит обнаруживающая и исправляющая способность циклического кода.

Выбор образующего полинома является ответственной задачей, так как корректирующие возможности разрабатываемого кода, алгоритмы и схемы кодирования и декодирования определяются этим полиномом. Общий вид образующего полинома: g (x) = a_r x^r + a_r-1 x^r-1 + . . . + a₁ x¹ + a₀ x⁰.

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

Степень образующего полинома, численно равная количеству проверочных элементов, определяется из соотношений:

 при нечетном d₀; (10)

 при четном d₀, (11)

где i = 0, 1, 2, … .

Решить неравенства (10) и (11) можно методом подбора: определяется минимальное значение n, при котором неравенства выполняются.

В условиях курсового проектирования можно ограничиться значениями n от двух до пяти. В реальных системах образующие полиномы стандартизированы и степень их составляет 12, 16, 24, 32 (возможны и другие варианты). Например, технология Х.25 предусматривает кодирование полиномом g(x) = x¹⁶ + x¹² + x⁵ + 1.

Образующие полиномы (многочлены) от 1-й до 5-й степени приведены в табл. 4 1.

Таблица 4

Неприводимые многочлены

Степень многочлена	Вид многочлена	Степень многочлена	Вид многочлена
1 2 3 4	х + 1 х2 + х + 1 х3 + х2 + 1, х3 + х + 1 х4 + х + 1, х4 + х3 + 1, х4 + х3 + х2 + х + 1	5	х5 + х2 + 1, х5 + х3 + 1, х5 + х3 + х2 + х + 1, х5 + х4 + х2 + х + 1, х5 + х4 + х3 + х + 1, х5 + х4 + х3 + х + 1

Итак, в данном разделе расчет по формуле (8) производился дважды: сначала предварительный – для определения кратности обнаруживаемых или исправляемых ошибок (при n = k), затем – уточняющий (при n = k + r) – для проверки полученного при применении циклического кода значения Р_{ош к} с исключением из общей суммы вероятностей обнаруживаемых или исправляемых ошибок определенной предыдущим расчетом кратности.