Принципы обнаружения и исправления ошибок циклическими кодами

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

В общем виде принятая комбинация h(x) в полиномиальном представлении равна сумме h(x)=f(x)+e(x),

где f(x)-многочлен, соответствующий переданной кодовой комбинации,

e(x)-многочлен, соответствующий вектору ошибок.

Ошибки обнаруживаются, если остаток от деления h(x) на Р(х) не равен нулю. Если же остаток равен нулю, то ошибка или отсутствует, или не обнаруживается кодом.

Исправление ошибок является гораздо более трудной задачей, чем обнаружение. Реализация такой операции возможна,

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

1. Принятое сообщение делится на Р(х) и вычисляется ос­таток.

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

3. Найденный многочлен е (х) вычитается из h (х), в ре­зультате получается f (x), т. е. переданное сообщение.

Другая, применяемая на практике процедура обнаружения и исправления ошибок циклическими кодами, основывается на том, что комбинации циклического кода являются нулевым про­странством по отношению к его проверочной матрице Н. Из этого свойства следует, что произведение вектора любой ком­бинации, принадлежащей циклическому коду, на матрицу Н^т равно нулю. Если же в принятой комбинации содержатся ошиб­ки и эта комбинация попадает в число запрещенных, то резуль­тат умножения, называемый синдромом, не будет равен нулю. Обозначив синдром через S = (s₀, s₁...s_n-k-1) будем иметь

(h_0,h₂,h₁…h_n-1)*H^T=(s₀s₁…s_n-k-1), (2.12)

где вектор (h₀h₁h₂…h_n-1)соответствует многочлену принятой комбинации h(x), равному h (х) = f (x) -f e (х). Таким обра­зом, ошибки обнаруживаются, если синдром S не равен нулю.

Исправить можно только те конфигурации ошибок в комби­нации, которые дают различные ненулевые синдромы.

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

3. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ОДНОКРАТНЫЕ ОШИБКИ

Устройство, позволяющее преобразовать комбинации исход­ного k-элементного кода в комбинации циклического кода, на­зывают кодирующим.

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

Рассмотрим пример построения и принцип работы кодирую­щего устройства кода (15.11) для производящего многочлена Р(х) = 1 + х +x⁴ (рис. 3.1). Элементы комбинации, соответст­вующей многочлену φ (х), поступают на выходной сумматор, что реализует умножение х^n-kφ (х) = х⁴φ (х).

Pиc. 3.1. Кодирующее устройство системати­ческого кода (15, 11) с образующим много­членом р(х) = 1 + x+x⁴

В течение k тактов, пока на вход поступают информацион­ные элементы, ключ Кл. находится в положении 1, при этом информационные элементы без всякой задержки поступают на выход кодирующего устройства. С приходом последнего инфор­мационного элемента в регистре сдвига определяется остаток от деления х^n-kφ (х) на Р (х), после чего ключ Кл. переклю­чается в положение 2 и на выход вслед за информационными элементами считывается остаток R(x), т. е. проверочные элемен­ты. Таким образом, с выхода кодирующего устройства поступа­ет комбинация циклического кода.

Кодирующее устройство несистематического (п,k)-кода реа­лизует умножение φ(х)Р(х). Схема построения КУ для кода (15, 11) с образующим полиномом Р (х) = 1 + х + x⁴ представ­лена на рис. 3.2.

Рис. 3.2. Кодирующее устройство несистематическо­го циклического (15, 11)-кода с образующим мно­гочленом р (х)= 1 + х + х⁴

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

Любой систематический (п,k)-код, исправляющий однократ­ные ошибки, должен иметь такое число п — k проверочных раз­рядов в комбинации, чтобы удовлетворялось неравенство 2^n-k≥n+1. Код, построенный таким образом, обеспечивает мини­мальное кодовое расстояние между любыми разрешенными ком­бинациями, равное трем.

Как было показано, любая одиночная ошибка может обна­руживаться по ненулевому остатку от деления многочлена h(x), соответствующего принятой комбинации, на производящий мно­гочлен Р (х). Однако для исправления однократных ошибок требуется, чтобы любой ошибке соответствовал определенный отличный от нуля остаток и, во-вторых, чтобы все эти остатки были различны между собой, т. е., чтобы выполнялось взаимо­однозначное соответствие между местоположением ошибки и ее остатком. Эти требования выполняются, если остатки в случае одиночных ошибок будут представлять собой степени первооб­разного элемента, являющегося корнем примитивного много­члена Р(х), и, следовательно, будут ненулевыми элементами поля Галуа GF(2ⁿ). Таких различных ненулевых элементов поля GF(2^т) будет 2^m —1. Пусть на i-й позиции комбинации длины n = 2^т —I произошла ошибка, которой соответствует одночлен е (х) = хⁱ. В результате деления принятой комбина­ции на производящий многочлен Р(х) образуется остаток R(x), представляющий собой элемент а¹ поля GF(2^m), где а — перво­образный элемент поля и корень многочлена Р (х). Этот оста­ток будет содержаться в регистре сдвига, который реализует операцию деления на многочлен Р (х). При этом сдвиг содер­жимого регистра на один шаг соответствует умножению на х с последующим приведением результата по модулю Р (х). Следо­вательно, произведя (п — i) сдвигов остатка R (х), мы тем са­мым как бы умножили принятую комбинацию h (х) на х^n-1 и разделили результат на Р (х). В регистре при этом останется некоторый новый остаток R_i (х) = x^n-iR (x) [modP(x)]. Со­стояние регистра определим из преобразования:

х^п-ih(х)=х^n-i[ f(x)+ е(х)]=x^n-if(х)+х^п-iе(х)≡хⁿ ≡1[modP(x)],

где f (х) — разрешенная кодовая комбинация, выраженная в виде многочлена, делящегося на Р (х) без остатка. Следова­тельно, состояние регистра после (n — i) сдвигов будет соот­ветствовать элементу поля а°= 1. Обнаружив это состояние, можно легко исправить одиночную ошибку.

Рассмотрим процесс исправления одиночных ошибок деко­дирующим устройством (рис. 3.3) циклического (15,11)кода, производящий многочлен которого имеет вид Р (х) =1+ х+x⁴ Комбинация циклического кода поступает на вход буферного накопителя емкостью п =15 и одновременно с этим на вход регистра сдвига с обратными связями. Когда элементы комби­нации циклического кода заполнят буфер, в регистре сдвига с обратными связями будет содержаться остаток от деления при­нятой комбинации на производящий многочлен Р (х).

Рис. 3.3. Декодирующее устройство циклического кода (15, 11), исправляющего однократные ошибки

Как было показано, определение ошибочной i-й позиции для рассматриваемого кода осуществляется путем обнаружения со­стояния (1000) через (п — i) сдвигов, т. е. тогда, когда ошибоч­ный элемент уже покинет буфер. Следовательно, после буфер­ного накопителя необходимо поставить задержку на один эле­мент, что позволит исправить эту ошибку со следующим так­том (сдвигом). Чтобы предотвратить ложную работу декоди­рующего устройства во время заполнения комбинацией буфера, а также при наличии в принятой комбинации одиночной ошиб­ки на нулевой позиции, соответствующей коэффициенту при х°, поставлен ключ Кл. Этот ключ замыкается в момент поступле­ния на выходной сумматор 111 первого информационного эле­мента, соответствующего коэффициенту при х¹⁴ в принятой ком­бинации, а размыкается в момент сброса регистра сдвига с обратными связями, т. е. в момент установления состояния 0000. Сброс можно осуществить, например, из блока обнаружения в момент исправления ошибки подачей единицы в сумматор 11.

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

Дата добавления: 2015-07-16