dmitriev_8

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

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

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

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

Число ошибок такого вида В4 для блока из lхn символов равно

Общее число четырехкратных ошибок составляет

Таким образом, отношение числа не обнаруживаемых четырехкратных ошибок к общему числу таких ошибок

Определим минимальный вес ненулевого вектора рассматриваемого итеративного кода (двумерной кодовой комбинации). Такой вектор должен содержать только одну ненулевую вектор-строку, минимальный вес, которой равен 2. Проверка на четность каждого из ненулевых столбцов также дает вектор веса 2. Следовательно, минимальный вес ненулевого вектора итеративного кода с двойной проверкой на четность равен 2*2 = 4.

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

где dγ — кодовое расстояние линейного кода по координате γ.

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

Такая процедура проста, но снижает корректирующую способность итеративного кода, поскольку оказывается невозможным исправить часть ошибок кратности (d-l)/2.

Поясним это на примере итерации двух кодов Хэмминга (7, 4). Результирующий итеративный код (49, 16) имеет минимальное кодовое расстояние, равное 3x3 = =9, и, следовательно, потенциально, как любой линейный код, способен исправлять все ошибки кратности 4 и менее. Однако, применяя указанную выше процедуру декодирования, невозможно исправить четырехкратные ошибки с расположением искаженных символов

в вершинах прямоугольника (рис. 6.26).

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

Рассмотрим один из таких кодов [4].

Стандартный код для записи информации на магнитную ленту. В

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

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

Расположение кодируемого кадра информации на ленте показано на рис. 6.27.

Кодирование циклическим кодом осуществляется следующим образом.

Многочлен F1(x), соответствующий информации перкой строки, умножается на x и результат приводится по модулю образующего многочлена g(x) степени n, где n — число дорожек, включая контрольную [например, для 9 дорожек g(x) = (х + 1)(х8 + + х4 + х3 + x2 + 1)]. Полученный остаток Ri(x) суммируется по модулю два с многочленом F2(x), соответствующим информации второй строки. Сумма снова умножается на x и далее приводится по модулю g(x), в результате чего определяется остаток R2(x). Применив этот алгоритм последовательно ко всем строкам кодируемого кадра информации, получим R1(x) — многочлен степени не выше n-1, который и записывается в конце кадра (при нечетном числе строк в нем), в качестве символов контроля по дорожкам

где Ri(x) mod (x) означает величину Ri(x), приведенную по модулю g(x). Декодирование производится аналогично кодированию, причем

участвует и контрольная строка — Ri(x). Процесс декодирования можно записать следующим образом:

где Ε (x) — некоторый многочлен, определяющий ошибку. Выражение M(х) можно представить в виде

Сравнивая его с выражением (6.58), можно заключить, что при отсутствии ошибки будет фиксироваться значение R'(x), равное нулю. Случай R'(x) неравна 0 соответствует обнаружению ошибки. Если имела место пачка ошибок вдоль одной из дорожек, то она может быть исправлена. Многочлен ошибки в этом случае имеет вид Ε (x) = xje(х), где е(х) отражает поразрядную структуру, а хj — адрес ошибки. Так как справедливо равенство

(6.59), то

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

исходя из следующих соображений. Предположив, что на ленте была записана информация, состоящая из одних нулей, т. е. F1(x) = 0...Fl(x) = 0, Rl(x) = 0 и при считывании на дорожке с выбранным известным номером n возникла пачка ошибок с точно такой же структурой е(х), в результате декодирования получим некоторый многочлен R"(x), причем

где k — число дорожек, на которое отстоит дорожка с известным номером η от дорожки, где возникла пачка ошибок.

Таким образом, если пачка ошибок возникла только по одной дорожке, то, умножив R'(x) на xk с приведением по модулю g(x), получим R"(x). Поэтому при декодировании одновременно с вычислением R'(x) осуществляется вычисление R"(x). Для определения номера дорожки с искаженными символами производится последовательное домножение R'(x)

на х, х2, ..., хn-1.

На каждом шаге, начиная с R'(x), результат приводится по модулю g(x) и затем сравнивается с R"(x). Процесс прекращается, как только на какомлибо i-м шаге зафиксировано равенство (в этом случае k = i— 1 и известная величина n определяет номер искомой дорожки) или после проведения n сравнений. В последнем случае фиксируется наличие неисправимой ошибки.

При четном числе строк кодируемой информации l образующий многочлен типа g(x) = (х + 1 )g'(x) обеспечивает Rl(x) всегда с четным числом членов. Суммирование этого многочлена с g'(x) позволяет получить результирующий многочлен R'l(x), удовлетворяющий проверке по нечетности вдоль строки.

Описанные коды способны исправлять все пачки ошибок, возникающие по одной дорожке, за исключением пачек вила

где L(x) — произвольный многочлен.

Кодирование и декодирование информации с использованием рассматриваемых кодов относительно просто реализуется как программными, так и аппаратными средствами [4].

§ 6.11 СВЕРТОЧНЫЕ КОДЫ

Для сверточных (рекуррентных) кодов характерно, что операции кодирования и декодирования осуществляются над непрерывной последовательностью символов. Такой метод имеет определенные преимущества, так как предоставляет большие возможности для использования вводимой избыточности.

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

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

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

Способы реализации сверточных кодов во многом похожи на способы реализации циклических кодов.

Процессы кодирования и декодирования таких кодов можно описать посредством многочленов с использованием оператора задержки D. Последовательности символов, поступающие на каждый из входов, представляют многочленами, где ct(i)— символ, появляющийся на j-м выходе кодирующего устройства в момент τ.

Связь между информационными и проверочными символами задается образующими многочленами сверточного кода.

Степени образующих многочленов не превышают числа т, а коэффициентами Mjk для двоичных кодов являются элементы поля GF(2).

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

В процессе прохождения по каналу связи передаваемые символы могут искажаться. Запишем последовательности информационных и проверочных символов, поступивших из канала связи, в виде многочленов и

здесь Ut(i) символ j-й информационной последовательности, поступившей в момент τ(j=1,2,…,k); Ut(i) — символ i-й проверочной последовательности, поступившей в момент τ(i= k+l, k + 2, ...,n).

Аналогично запишем последовательности ошибок, содержащие

единицы на местах искаженных символов и нули во всех остальных позициях:

где et(j) — символ ошибки, имеющей место в j'-й информационной последовательности в момент τ (у = 1, 2, ..., k).

— символ ошибки, имеющей место в i-й проверочной последовательности в момент τ (i = k + 1, k + 2, ..., n).

Очевидно,

В процессе декодирования по информационным символам, поступающим из канала связи, с использованием образующих многочленов снова формируются последовательности проверочных символов Ul(i)(D)

Последовательности Ul(i)(D) и U(i)(D) (i = k+l, k + 2, ..., n) сравниваются между собой, в результате чего получаем последовательности S(i)(D), определяющие структуру ошибок. Эти последовательности по аналогии с блоковыми кодами называют синдромами

Подставляя выражения (6.63) и (6.64) в (6.66), получаем

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

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

На рис. 6.29 приведена схема кодирующего устройства для простейших сверточных кодов, у которых на k информационных символов приходится один проверочный. За время цикла входной коммутатор СК1 направляет k символов входной последовательности в k

информационных каналов, с которых они поступают как непосредственно на выход, так и на линейный преобразователь П, формирующий проверочный символ Ck+1· В случае двоичного кодирования преобразователь включает ячейки памяти, объединенные в регистры сдвига, устройства

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

В декодирующем устройстве (рис. 6.30) информационные символы последовательности, поступающей из канала связи, также разделяются с

помощью коммутатора CK1 по k информационным каналам. Посредством линейного преобразователя П, аналогичного преобразователю кодирующего устройства, снова формируются проверочные символы Ck+1, которые сравниваются (суммируются по модулю два) с проверочными символами, поступающими непосредственно из канала связи. В случае отсутствия ошибок образующаяся на выходе последовательность символов состоит из одних нулей.

Очевидно, что в процессе сравнения единица в синдроме может и не образовываться, если одновременно окажется искаженным не только информационный символ, но и проверочный, сформированный с участием данного информационного символа. Чтобы исключить такую возможность, информационные и соответствующие им проверочные символы разносятся в канале по времени передачи, что осуществляется посредством ячеек памяти преобразователя. Предполагается, что за пачкой ошибок следует определенное число неискаженных символов. Поэтому одновременное искажение информационных и зависящих от них проверочных символов считается невозможным. Если же длина пачки ошибок превысит значение, на которое рассчитывается код, или между пачками ошибок не будет необходимого числа неискаженных символов, то сверточный код не обеспечивает исправления ошибок. Более того, в этом случае может произойти «исправление» правильно принятого информационного символа на неправильный. Анализатор синдрома, входящий в состав блока коррекции, представляет собой логическую схему, определяющую, к какой информационной последовательности относится очередной искаженный символ, и формирующую соответствующий импульс коррекции.

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