В предыдущем параграфе было дано описание кодов Хэмминга как циклических кодов, порождающие многочлены которых имеют корень в соответствующем расширении основного поля. Описанные коды исправляют одну ошибку. Сейчас мы возвращаемся к исправляющим две ошибки кодам над полем GF (2). Пусть длина кода имеет вид 
для некоторого 
и пусть а — примитивный элемент поля 
Мы рассмотрим те даоичиые коды, для которых а и а? являются корнями порождающих многочленов, и покажем, что такие коды позволяют исправлять две ошибки.
Пусть 
многочлен наименьшей степени, для которого 
из 
являются корнями. Описав процедуру декодирования, позволяющую исправлять все одиночные и двойные ошибки, мы докажем, что минимальное расстояние этого кода равно по меньшей мере 5.
Принятое слово записывается многочленом степени 
вида
где 
содержит не более двух ненулевых коэффициентов, поскольку мы рассматриваем случай исправления не более двух ошибок. Таким образом, или 
или с 
или 
Целые числа 
и 
маркируют позиции, в которых произошли ошибки. Для маркировки ошибочных позиций мы будем также использовать элементы поля 
Элемент поля а соответствует компоненте с номером 
. В этой роли элементы поля называются локаторами. Обозначим — 
Так как длина кода 
равна порядку элемента а, то локаторы А, и 
определяются однозначно. Если произошла только одна ошибка, то положим 
если ошибок не произошло, то 
.
Пусть 
Эти элементы, известные также под названием компонент синдрома, вычисляются непосредственно по принятому слову 
Так как 
являются корнями 
то 
Предположим, что произошли две ошибки: 
Но это в точности дает систему двух уравнений относительно двух неизвестных 
в поле 
Если может произойти не более двух ошибок, то величина равна нулю тогда и только тогда, когда не произошло ни одной ошибки. Декодер должен продолжать работу в том случае, когда 
отлично от нуля. Если выписанная система из двух нелинейных уравнений однозначно разрешима относительно 
то две ошибки могут быть исправлены, и минимальное расстояние рассматриваемого кода равно по меньшей мере 5.
Прямого очевидного способа решения такой системы нет. Один из методов состоит во введении нового многочлена, определяемого так, чтобы локаторы ошибок были его корнями:
Если мы сумеем найти коэффициенты этого многочлена, то, разложив его на линейные множители, мы сможем найти 
Но над расширением поля 
Таким образом,
если произошли одна или две ошибки. Многочлен в правой части нам известен, поскольку известны 
Локаторы ошибок являются корнями этого многочлена, а корни любого многочлена над полем определяются однозначно. Следовательно, код исправляет две ошибки.
Указав процедуру декодирования, мы установили, что выбранный многочлен 
порождает код, исправляющий две произвольные ошибки. Практически можно использовать любую удобную процедуру декодирования, и одной из них является процедура вычисления корней выписанного выше квадратного уравнения в 
Так как всего имеется 
возможностей выбора каждого из корней, то это часто делается методом проб и ошибок. Другие схемы декодирования будут рассмотрены в следующих главах.
Рассмотренные в настоящем параграфе коды, исправляющие две ошибки, служат иллюстрацией того, как построить
циклические коды над некоторым полем, используя лежащие в большем поле корни порождающих эти коды многочленов. В гл. 7 будет рассмотрен общий случай такого построения для произвольного поля символов 
и произвольного числа исправляемых ошибок.
In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction.
If 00010111 is a valid codeword, applying a right circular shift gives the string 10001011. If the code is cyclic, then 10001011 is again a valid codeword. In general, applying a right circular shift moves the least significant bit (LSB) to the leftmost position, so that it becomes the most significant bit (MSB); the other positions are shifted by 1 to the right.
Definition[edit]
Let 
Cyclic codes have some additional structural constraint on the codes. They are based on Galois fields and because of their structural properties they are very useful for error controls. Their structure is strongly related to Galois fields because of which the encoding and decoding algorithms for cyclic codes are computationally efficient.
Algebraic structure[edit]
Cyclic codes can be linked to ideals in certain rings. Let ![R=A[x]/(x^{n}-1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/8595f12ff1f64bc73a4e3e03851397cc877af6e2)
This must be a divisor of 
If the generator polynomial 
The idempotent of 
An irreducible code is a cyclic code in which the code, as an ideal is irreducible, i.e. is minimal in
Examples[edit]
For example, if 
.
It corresponds to the ideal in ![mathbb {F} _{2}[x]/(x^{3}-1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b419295ea611763fd442a22f8f56fe8dc30c023)
The polynomial
The idempotent of this code is the polynomial 
Trivial examples[edit]
Trivial examples of cyclic codes are 
Over 
Quasi-cyclic codes and shortened codes[edit]
Before delving into the details of cyclic codes first we will discuss quasi-cyclic and shortened codes which are closely related to the cyclic codes and they all can be converted into each other.
Definition[edit]
Quasi-cyclic codes:[citation needed]
An 
Here, codeword polynomial is an element of a linear code whose code words are polynomials that are divisible by a polynomial of shorter length called the generator polynomial. Every codeword polynomial can be expressed in the form 
Definition[edit]
Shortened codes:
An ![[n,k]](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d9e3e5f03db243c10e64608605d156ae1885952)
In shortened codes information symbols are deleted to obtain a desired blocklength smaller than the design blocklength. The missing information symbols are usually imagined to be at the beginning of the codeword and are considered to be 0. Therefore, 
All the symbols which are dropped need not be transmitted and at the receiving end can be reinserted. To convert
Cyclic codes for correcting errors[edit]
Now, we will begin the discussion of cyclic codes explicitly with error detection and correction. Cyclic codes can be used to correct errors, like Hamming codes as cyclic codes can be used for correcting single error. Likewise, they are also used to correct double errors and burst errors. All types of error corrections are covered briefly in the further subsections.
The (7,4) Hamming code has a generator polynomial 
The received word is a polynomial of degree
where 
We define the Syndrome Polynomial, 
For correcting two errors[edit]
Let the field elements 
Let 
These field elements are called «syndromes». Now because 
And these two can be considered as two pair of equations in
Hence if the two pair of nonlinear equations can be solved cyclic codes can used to correct two errors.
Hamming code[edit]
The Hamming(7,4) code may be written as a cyclic code over GF(2) with generator 
![[2^{r}-1,2^{r}-r-2,4]](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbf755cb5b384b44e604aa2cc03660048b528348)
Hamming code for correcting single errors[edit]
A code whose minimum distance is at least 3, have a check matrix all of whose columns are distinct and non zero. If a check matrix for a binary code has 
It is easy to define Hamming codes for large alphabets of size 
So, there are 
![[(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]](https://wikimedia.org/api/rest_v1/media/math/render/svg/6447e6a6ef3646859efcaa879911eae094aae869)
Now, for cyclic codes, Let 
But for 
where, 
But we can also use 
Cyclic codes for correcting burst errors[edit]
From Hamming distance concept, a code with minimum distance 
A cyclic burst of length
In polynomial form cyclic burst of length 
A linear block code that corrects all burst errors of length 
This property is also known as Rieger bound and it is similar to the Singleton bound for random error correcting.
Fire codes as cyclic bounds[edit]
In 1959, Philip Fire[6] presented a construction of cyclic codes generated by a product of a binomial and a primitive polynomial. The binomial has the form 
where 
A fire code can correct all burst errors of length t or less if no two bursts 
This shows that 
for some 
Since 
Fire codes are the best single burst correcting codes with high rate and they are constructed analytically. They are of very high rate and when 
For error detection cyclic codes are widely used and are called
Cyclic codes on Fourier transform[edit]
Applications of Fourier transform are widespread in signal processing. But their applications are not limited to the complex fields only; Fourier transforms also exist in the Galois field
Fourier transform over finite fields[edit]
Fourier transform over finite fields
The discrete Fourier transform of vector 
where exp(
If 
Here 
In Galois field time domain vector
Spectral description of cyclic codes[edit]
Any codeword of cyclic code of blocklength 
Thus, cyclic codes can also be defined as
Given a set of spectral indices, 
So, cyclic codes are vectors in the field
Following are the few bounds on the spectrum of cyclic codes.
BCH bound[edit]
If 
Hartmann-Tzeng bound[edit]
If
components 
Roos bound[edit]
If 
Quadratic residue codes[edit]
When the prime 
Generalizations[edit]
A constacyclic code is a linear code with the property that for some constant λ if (c1,c2,…,cn) is a codeword then so is (λcn,c1,…,cn-1). A negacyclic code is a constacyclic code with λ=-1.[8] A quasi-cyclic code has the property that for some s, any cyclic shift of a codeword by s places is again a codeword.[9] A double circulant code is a quasi-cyclic code of even length with s=2.[9] Quasi-twisted codes and multi-twisted codes are further generalizations of constacyclic codes.[10][11]
See also[edit]
- Cyclic redundancy check
- BCH code
- Reed–Muller code
- Binary Golay code
- Ternary Golay code
- Eugene Prange
Notes[edit]
- ^ Van Lint 1998, p. 76
- ^ Van Lint 1998, p. 80
- ^ Hill 1988, pp. 159–160
- ^ Blahut 2003, Theorem 5.5.1
- ^ Hill 1988, pp. 162–163
- ^ P. Fire, E, P. (1959). A class of multiple-error-correcting binary codes for non-independent errors. Sylvania Reconnaissance Systems Laboratory, Mountain View, CA, Rept. RSL-E-2, 1959.
- ^ Wei Zhou, Shu Lin, Khaled Abdel-Ghaffar. Burst or random error correction based on Fire and BCH codes. ITA 2014: 1-5 2013.
- ^ Van Lint 1998, p. 75
- ^ a b MacWilliams & Sloane 1977, p. 506
- ^ Aydin, Nuh; Siap, Irfan; K. Ray-Chaudhuri, Dijen (2001). «The Structure of 1-Generator Quasi-Twisted Codes and New Linear Codes». Designs, Codes and Cryptography. 24 (3): 313–326. doi:10.1023/A:1011283523000. S2CID 17376783.
- ^ Aydin, Nuh; Halilović, Ajdin (2017). «A generalization of quasi-twisted codes: multi-twisted codes». Finite Fields and Their Applications. 45: 96–106. doi:10.1016/j.ffa.2016.12.002. S2CID 7694655.
References[edit]
- Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press, ISBN 0-521-55374-1
- Hill, Raymond (1988), A First Course In Coding Theory, Oxford University Press, ISBN 0-19-853803-0
- MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York: North-Holland Publishing, ISBN 0-444-85011-2
- Van Lint, J. H. (1998), Introduction to Coding Theory, Graduate Texts in Mathematics 86 (3rd ed.), Springer Verlag, ISBN 3-540-64133-5
Further reading[edit]
- Ranjan Bose, Information theory, coding and cryptography, ISBN 0-07-048297-7
- Irving S. Reed and Xuemin Chen, Error-Control Coding for Data Networks, Boston: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4.
- Scott A. Vanstone, Paul C. Van Oorschot, An introduction to error correcting codes with applications, ISBN 0-7923-9017-2
External links[edit]
- John Gill’s (Stanford) class notes – Notes #3, October 8, Handout #9, EE 387.
- Jonathan Hall’s (MSU) class notes – Chapter 8. Cyclic codes — pp. 100 — 123
- David Terr. «Cyclic Code». MathWorld.
This article incorporates material from cyclic code on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction.
If 00010111 is a valid codeword, applying a right circular shift gives the string 10001011. If the code is cyclic, then 10001011 is again a valid codeword. In general, applying a right circular shift moves the least significant bit (LSB) to the leftmost position, so that it becomes the most significant bit (MSB); the other positions are shifted by 1 to the right.
Definition[edit]
Let
Cyclic codes have some additional structural constraint on the codes. They are based on Galois fields and because of their structural properties they are very useful for error controls. Their structure is strongly related to Galois fields because of which the encoding and decoding algorithms for cyclic codes are computationally efficient.
Algebraic structure[edit]
Cyclic codes can be linked to ideals in certain rings. Let
This must be a divisor of
If the generator polynomial
The idempotent of
An irreducible code is a cyclic code in which the code, as an ideal is irreducible, i.e. is minimal in
Examples[edit]
For example, if
It corresponds to the ideal in
The polynomial
The idempotent of this code is the polynomial
Trivial examples[edit]
Trivial examples of cyclic codes are
Over
Quasi-cyclic codes and shortened codes[edit]
Before delving into the details of cyclic codes first we will discuss quasi-cyclic and shortened codes which are closely related to the cyclic codes and they all can be converted into each other.
Definition[edit]
Quasi-cyclic codes:[citation needed]
An
Here, codeword polynomial is an element of a linear code whose code words are polynomials that are divisible by a polynomial of shorter length called the generator polynomial. Every codeword polynomial can be expressed in the form
Definition[edit]
Shortened codes:
An
In shortened codes information symbols are deleted to obtain a desired blocklength smaller than the design blocklength. The missing information symbols are usually imagined to be at the beginning of the codeword and are considered to be 0. Therefore,
All the symbols which are dropped need not be transmitted and at the receiving end can be reinserted. To convert
Cyclic codes for correcting errors[edit]
Now, we will begin the discussion of cyclic codes explicitly with error detection and correction. Cyclic codes can be used to correct errors, like Hamming codes as cyclic codes can be used for correcting single error. Likewise, they are also used to correct double errors and burst errors. All types of error corrections are covered briefly in the further subsections.
The (7,4) Hamming code has a generator polynomial
The received word is a polynomial of degree
where
We define the Syndrome Polynomial,
For correcting two errors[edit]
Let the field elements
Let
These field elements are called «syndromes». Now because
And these two can be considered as two pair of equations in
Hence if the two pair of nonlinear equations can be solved cyclic codes can used to correct two errors.
Hamming code[edit]
The Hamming(7,4) code may be written as a cyclic code over GF(2) with generator
Hamming code for correcting single errors[edit]
A code whose minimum distance is at least 3, have a check matrix all of whose columns are distinct and non zero. If a check matrix for a binary code has
It is easy to define Hamming codes for large alphabets of size
So, there are
Now, for cyclic codes, Let
But for
where,
But we can also use
Cyclic codes for correcting burst errors[edit]
From Hamming distance concept, a code with minimum distance
A cyclic burst of length
In polynomial form cyclic burst of length
A linear block code that corrects all burst errors of length
This property is also known as Rieger bound and it is similar to the Singleton bound for random error correcting.
Fire codes as cyclic bounds[edit]
In 1959, Philip Fire[6] presented a construction of cyclic codes generated by a product of a binomial and a primitive polynomial. The binomial has the form
where
A fire code can correct all burst errors of length t or less if no two bursts
This shows that
for some
Since
Fire codes are the best single burst correcting codes with high rate and they are constructed analytically. They are of very high rate and when
For error detection cyclic codes are widely used and are called
Cyclic codes on Fourier transform[edit]
Applications of Fourier transform are widespread in signal processing. But their applications are not limited to the complex fields only; Fourier transforms also exist in the Galois field
Fourier transform over finite fields[edit]
Fourier transform over finite fields
The discrete Fourier transform of vector
where exp(
If
Here
In Galois field time domain vector
Spectral description of cyclic codes[edit]
Any codeword of cyclic code of blocklength
Thus, cyclic codes can also be defined as
Given a set of spectral indices,
So, cyclic codes are vectors in the field
Following are the few bounds on the spectrum of cyclic codes.
BCH bound[edit]
If
Hartmann-Tzeng bound[edit]
If
components
Roos bound[edit]
If
Quadratic residue codes[edit]
When the prime
Generalizations[edit]
A constacyclic code is a linear code with the property that for some constant λ if (c1,c2,…,cn) is a codeword then so is (λcn,c1,…,cn-1). A negacyclic code is a constacyclic code with λ=-1.[8] A quasi-cyclic code has the property that for some s, any cyclic shift of a codeword by s places is again a codeword.[9] A double circulant code is a quasi-cyclic code of even length with s=2.[9] Quasi-twisted codes and multi-twisted codes are further generalizations of constacyclic codes.[10][11]
See also[edit]
- Cyclic redundancy check
- BCH code
- Reed–Muller code
- Binary Golay code
- Ternary Golay code
- Eugene Prange
Notes[edit]
- ^ Van Lint 1998, p. 76
- ^ Van Lint 1998, p. 80
- ^ Hill 1988, pp. 159–160
- ^ Blahut 2003, Theorem 5.5.1
- ^ Hill 1988, pp. 162–163
- ^ P. Fire, E, P. (1959). A class of multiple-error-correcting binary codes for non-independent errors. Sylvania Reconnaissance Systems Laboratory, Mountain View, CA, Rept. RSL-E-2, 1959.
- ^ Wei Zhou, Shu Lin, Khaled Abdel-Ghaffar. Burst or random error correction based on Fire and BCH codes. ITA 2014: 1-5 2013.
- ^ Van Lint 1998, p. 75
- ^ a b MacWilliams & Sloane 1977, p. 506
- ^ Aydin, Nuh; Siap, Irfan; K. Ray-Chaudhuri, Dijen (2001). «The Structure of 1-Generator Quasi-Twisted Codes and New Linear Codes». Designs, Codes and Cryptography. 24 (3): 313–326. doi:10.1023/A:1011283523000. S2CID 17376783.
- ^ Aydin, Nuh; Halilović, Ajdin (2017). «A generalization of quasi-twisted codes: multi-twisted codes». Finite Fields and Their Applications. 45: 96–106. doi:10.1016/j.ffa.2016.12.002. S2CID 7694655.
References[edit]
- Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2nd ed.), Cambridge University Press, ISBN 0-521-55374-1
- Hill, Raymond (1988), A First Course In Coding Theory, Oxford University Press, ISBN 0-19-853803-0
- MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York: North-Holland Publishing, ISBN 0-444-85011-2
- Van Lint, J. H. (1998), Introduction to Coding Theory, Graduate Texts in Mathematics 86 (3rd ed.), Springer Verlag, ISBN 3-540-64133-5
Further reading[edit]
- Ranjan Bose, Information theory, coding and cryptography, ISBN 0-07-048297-7
- Irving S. Reed and Xuemin Chen, Error-Control Coding for Data Networks, Boston: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4.
- Scott A. Vanstone, Paul C. Van Oorschot, An introduction to error correcting codes with applications, ISBN 0-7923-9017-2
External links[edit]
- John Gill’s (Stanford) class notes – Notes #3, October 8, Handout #9, EE 387.
- Jonathan Hall’s (MSU) class notes – Chapter 8. Cyclic codes — pp. 100 — 123
- David Terr. «Cyclic Code». MathWorld.
This article incorporates material from cyclic code on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
Основной недостаток применения групповых
линейных кодов – сложность кодирующих
и декодирующих устройств, являющихся
устройствами параллельного типа. Переход
к циклическим кодам позволяет упростить
схемную реализацию кодирующих и
декодирующих устройств за счет
многотактных способов обработки
циклических кодов с помощью сдвиговых
регистров. Таким образом, в системах,
использующих циклические коды,
«обменивают» увеличение времени
кодирования и декодирования на упрощение
аппаратуры. Циклическим кодом называют
такой групповой код, который замкнут
относительно циклической перестановки
любой кодовой комбинации этого кода,
т.е. в результате циклической перестановки
любого кодового вектора получается
кодовый вектор, принадлежащий этому же
циклическому коду.
Циклической перестановкой называется
такая перестановка, при которой все
разряды смещаются в сторону старших
разрядов, причем последний разряд
переходит на место первого.
1.2 Построение цк
Циклическим кодом называется циклического
векторное пространство, обладающее
всеми свойствами группового кода, но
замкнутого не только относительно
линейных операций, но и относительно
операции циклического сдвига. В результате
циклического сдвига любого кодового
вектора получается кодовый вектор,
принадлежащий этому же векторному
пространству. В основе циклических
кодов лежит алгебра полиномов по модулю
над
пространственным полем (полем Галуа).
Циклическим сдвигом называется такой
сдвиг, при котором все разряды смещаются
в сторону старших разрядов, причем
последний разряд переходит на место
первого.
Пусть
Тогда после циклического сдвига получим
Математической основой построения
циклических кодов является представление
любого двоичного числа в виде полинома,
содержащего переменную Х, причем двоичные
цифры являются коэффициентами при этой
переменной.
Пример 1
В дальнейшем, если нет особых замечаний,
высшие степени пишем справа. Над такими
полиномами можно производить все
операции согласно законам алгебры.
Однако при всех операциях суммирование
производиться по модулю 2 (без переносов
в старшие разряды в отличие от
арифметического суммирования).
Вычитание, используемое при делении
полиномов, также необходимо осуществлять
по модулю два (mod2), и оно
заменяется эквивалентной операцией
суммирования поmod2.
Пример 2
Циклический код полностью задаётся
так называемым порождающим полиномом
g(x) степениk, гдеk–
число контрольных (избыточных) символов
циклического кода.
Кодовые комбинации циклического кода
строятся так, чтобы соответствующие им
полиномы делились без остатка на g(x).
С другой стороны, циклический код может
быть полностью определен многочленомh(x) степениm, гдеm–
число информационных символов циклического
кода:
(1)
n– число разрядов (длина)
циклического кода (n=m+k):
Полином, соответствующий кодовой
комбинации циклического кода, имеет
вид:
Циклические коды, исправляющие одну
ошибку (
),
либо исправляющие одну и обнаруживающие
две ошибки (
)
называются циклическими кодами Хемминга.
Для циклических кодов Хемминга имеет
место
Пример 3
Наибольший интерес представляют
систематические циклические коды, так
как они позволяют наиболее просто
реализовать кодирующие и декодирующие
устройства. Условимся в любом
систематическом циклическом коде первые
символов, т.е. коэффициенты при
всегда
выбирать в качестве проверочных символов,
а последниеmсимволов,
т.е. коэффициенты при
— в качестве информационных символов.
Соседние файлы в папке Теория
- #
- #
- #
- #
- #
03.07.20181.15 Mб3Теория.mht
- #
Корректирующие (или помехоустойчивые) коды — это коды, которые могут обнаружить и, если повезёт, исправить ошибки, возникшие при передаче данных. Даже если вы ничего не слышали о них, то наверняка встречали аббревиатуру CRC в списке файлов в ZIP-архиве или даже надпись ECC на планке памяти. А кто-то, может быть, задумывался, как так получается, что если поцарапать DVD-диск, то данные всё равно считываются без ошибок. Конечно, если царапина не в сантиметр толщиной и не разрезала диск пополам.
Как нетрудно догадаться, ко всему этому причастны корректирующие коды. Собственно, ECC так и расшифровывается — «error-correcting code», то есть «код, исправляющий ошибки». А CRC — это один из алгоритмов, обнаруживающих ошибки в данных. Исправить он их не может, но часто это и не требуется.
Давайте же разберёмся, что это такое.
Для понимания статьи не нужны никакие специальные знания. Достаточно лишь понимать, что такое вектор и матрица, как они перемножаются и как с их помощью записать систему линейных уравнений.
Внимание! Много текста и мало картинок. Я постарался всё объяснить, но без карандаша и бумаги текст может показаться немного запутанным.
Каналы с ошибкой
Разберёмся сперва, откуда вообще берутся ошибки, которые мы собираемся исправлять. Перед нами стоит следующая задача. Нужно передать несколько блоков данных, каждый из которых кодируется цепочкой двоичных цифр. Получившаяся последовательность нулей и единиц передаётся через канал связи. Но так сложилось, что реальные каналы связи часто подвержены ошибкам. Вообще говоря, ошибки могут быть разных видов — может появиться лишняя цифра или какая-то пропасть. Но мы будем рассматривать только ситуации, когда в канале возможны лишь замены нуля на единицу и наоборот. Причём опять же для простоты будем считать такие замены равновероятными.
Ошибка — это маловероятное событие (а иначе зачем нам такой канал вообще, где одни ошибки?), а значит, вероятность двух ошибок меньше, а трёх уже совсем мала. Мы можем выбрать для себя некоторую приемлемую величину вероятности, очертив границу «это уж точно невозможно». Это позволит нам сказать, что в канале возможно не более, чем 
ошибок. Это будет характеристикой канала связи.
Для простоты введём следующие обозначения. Пусть данные, которые мы хотим передавать, — это двоичные последовательности фиксированной длины. Чтобы не запутаться в нулях и единицах, будем иногда обозначать их заглавными латинскими буквами (
, 
, 
, …). Что именно передавать, в общем-то неважно, просто с буквами в первое время будет проще работать.
Кодирование и декодирование будем обозначать прямой стрелкой (
), а передачу по каналу связи — волнистой стрелкой (
). Ошибки при передаче будем подчёркивать.
Например, пусть мы хотим передавать только сообщения 
и 
. В простейшем случае их можно закодировать нулём и единицей (сюрприз!):
Передача по каналу, в котором возникла ошибка будет записана так:
Цепочки нулей и единиц, которыми мы кодируем буквы, будем называть кодовыми словами. В данном простом случае кодовые слова — это 
и 
.
Код с утроением
Давайте попробуем построить какой-то корректирующий код. Что мы обычно делаем, когда кто-то нас не расслышал? Повторяем дважды:
Правда, это нам не очень поможет. В самом деле, рассмотрим канал с одной возможной ошибкой:
Какие выводы мы можем сделать, когда получили 
? Понятно, что раз у нас не две одинаковые цифры, то была ошибка, но вот в каком разряде? Может, в первом, и была передана буква . А может, во втором, и была передана .
То есть, получившийся код обнаруживает, но не исправляет ошибки. Ну, тоже неплохо, в общем-то. Но мы пойдём дальше и будем теперь утраивать цифры.
Проверим в деле:
Получили 
. Тут у нас есть две возможности: либо это и было две ошибки (в крайних цифрах), либо это и была одна ошибка. Вообще, вероятность одной ошибки выше вероятности двух ошибок, так что самым правдоподобным будет предположение о том, что передавалась именно буква . Хотя правдоподобное — не значит истинное, поэтому рядом и стоит вопросительный знак.
Если в канале связи возможна максимум одна ошибка, то первое предположение о двух ошибках становится невозможным и остаётся только один вариант — передавалась буква .
Про такой код говорят, что он исправляет одну ошибку. Две он тоже обнаружит, но исправит уже неверно.
Это, конечно, самый простой код. Кодировать легко, да и декодировать тоже. Ноликов больше — значит передавался ноль, единичек — значит единица.
Если немного подумать, то можно предложить код исправляющий две ошибки. Это будет код, в котором мы повторяем одиночный бит 5 раз.
Расстояния между кодами
Рассмотрим поподробнее код с утроением. Итак, мы получили работающий код, который исправляет одиночную ошибку. Но за всё хорошее надо платить: он кодирует один бит тремя. Не очень-то и эффективно.
И вообще, почему этот код работает? Почему нужно именно утраивать для устранения одной ошибки? Наверняка это всё неспроста.
Давайте подумаем, как этот код работает. Интуитивно всё понятно. Нолики и единички — это две непохожие последовательности. Так как они достаточно длинные, то одиночная ошибка не сильно портит их вид.
Пусть мы передавали 
, а получили 
. Видно, что эта цепочка больше похожа на исходные , чем на 
. А так как других кодовых слов у нас нет, то и выбор очевиден.
Но что значит «больше похоже»? А всё просто! Чем больше символов у двух цепочек совпадает, тем больше их схожесть. Если почти все символы отличаются, то цепочки «далеки» друг от друга.
Можно ввести некоторую величину 
, равную количеству различающихся цифр в соответствующих разрядах цепочек 
и 
. Эту величину называют расстоянием Хэмминга. Чем больше это расстояние, тем меньше похожи две цепочки.
Например, 
, так как все цифры в соответствующих позициях равны, а вот 
.
Расстояние Хэмминга называют расстоянием неспроста. Ведь в самом деле, что такое расстояние? Это какая-то характеристика, указывающая на близость двух точек, и для которой верны утверждения:
- Расстояние между точками неотрицательно и равно нулю только, если точки совпадают.
- Расстояние в обе стороны одинаково.
- Путь через третью точку не короче, чем прямой путь.
Достаточно разумные требования.
Математически это можно записать так (нам это не пригодится, просто ради интереса посмотрим):
.
Предлагаю читателю самому убедиться, что для расстояния Хэмминга эти свойства выполняются.
Окрестности
Таким образом, разные цепочки мы считаем точками в каком-то воображаемом пространстве, и теперь мы умеем находить расстояния между ними. Правда, если попытаться сколько нибудь длинные цепочки расставить на листе бумаги так, чтобы расстояния Хэмминга совпадали с расстояниями на плоскости, мы можем потерпеть неудачу. Но не нужно переживать. Всё же это особое пространство со своими законами. А слова вроде «расстояния» лишь помогают нам рассуждать.
Пойдём дальше. Раз мы заговорили о расстоянии, то можно ввести такое понятие как окрестность. Как известно, окрестность какой-то точки — это шар определённого радиуса с центром в ней. Шар? Какие ещё шары! Мы же о кодах говорим.
Но всё просто. Ведь что такое шар? Это множество всех точек, которые находятся от данной не дальше, чем некоторое расстояние, называемое радиусом. Точки у нас есть, расстояние у нас есть, теперь есть и шары.
Так, скажем, окрестность кодового слова радиуса 1 — это все коды, находящиеся на расстоянии не больше, чем 1 от него, то есть отличающиеся не больше, чем в одном разряде. То есть это коды:
Да, вот так странно выглядят шары в пространстве кодов.
А теперь посмотрите. Это же все возможные коды, которые мы получим в канале в одной ошибкой, если отправим ! Это следует прямо из определения окрестности. Ведь каждая ошибка заставляет цепочку измениться только в одном разряде, а значит удаляет её на расстояние 1 от исходного сообщения.
Аналогично, если в канале возможны две ошибки, то отправив некоторое сообщение 
, мы получим один из кодов, который принадлежит окрестности радиусом 2.
Тогда всю нашу систему декодирования можно построить так. Мы получаем какую-то цепочку нулей и единиц (точку в нашей новой терминологии) и смотрим, в окрестность какого кодового слова она попадает.
Сколько ошибок может исправить код?
Чтобы код мог исправлять больше ошибок, окрестности должны быть как можно шире. С другой стороны, они не должны пересекаться. Иначе если точка попадёт в область пересечения, непонятно будет, к какой окрестности её отнести.
В коде с удвоением между кодовыми словами 
и 
расстояние равно 2 (оба разряда различаются). А значит, если мы построим вокруг них шары радиуса 1, то они будут касаться. Это значит, точка касания будет принадлежать обоим шарам и непонятно будет, к какому из них её отнести.
Именно это мы и получали. Мы видели, что есть ошибка, но не могли её исправить.
Что интересно, точек касания в нашем странном пространстве у шаров две — это коды и 
. Расстояния от них до центров равны единице. Конечно же, в обычно геометрии такое невозможно, поэтому рисунки — это просто условность для более удобного рассуждения.
В случае кода с утроением, между шарами будет зазор.
Минимальный зазор между шарами равен 1, так как у нас расстояния всегда целые (ну не могут же две цепочки отличаться в полутора разрядах).
В общем случае получаем следующее.
Этот очевидный результат на самом деле очень важен. Он означает, что код с минимальным кодовым расстоянием 
будет успешно работать в канале с ошибками, если выполняется соотношение
Полученное равенство позволяет легко определить, сколько ошибок будет исправлять тот или иной код. А сколько код ошибок может обнаружить? Рассуждения такие же. Код обнаруживает ошибок, если в результате не получится другое кодовое слово. То есть, кодовые слова не должны находиться в окрестностях радиуса других кодовых слов. Математически это записывается так:
Рассмотрим пример. Пусть мы кодируем 4 буквы следующим образом.
Чтобы найти минимальное расстояние между различными кодовыми словами, построим таблицу попарных расстояний.
| A | B | C | D | |
|---|---|---|---|---|
| A | — | 3 | 3 | 4 |
| B | 3 | — | 4 | 3 |
| C | 3 | 4 | — | 3 |
| D | 4 | 3 | 3 | — |
Минимальное расстояние 
, а значит 
, откуда получаем, что такой код может исправить до 
ошибок. Обнаруживает же он две ошибки.
Рассмотрим пример:
Чтобы декодировать полученное сообщение, посмотрим, к какому символу оно ближе всего.
Минимальное расстояние получилось для символа , значит вероятнее всего передавался именно он:
Итак, этот код исправляет одну ошибку, как и код с утроением. Но он более эффективен, так как в отличие от кода с утроением здесь кодируется уже 4 символа.
Таким образом, основная проблема при построении такого рода кодов — так расположить кодовые слова, чтобы они были как можно дальше друг от друга, и их было побольше.
Для декодирования можно было бы использовать таблицу, в которой указывались бы все возможные принимаемые сообщения, и кодовые слова, которым они соответствуют. Но такая таблица получилась бы очень большой. Даже для нашего маленького кода, который выдаёт 5 двоичных цифр, получилось бы 
варианта возможных принимаемых сообщений. Для более сложных кодов таблица будет значительно больше.
Попробуем придумать способ коррекции сообщения без таблиц. Мы всегда сможем найти полезное применение освободившейся памяти.
Интерлюдия: поле GF(2)
Для изложения дальнейшего материала нам потребуются матрицы. А при умножении матриц, как известно мы складываем и перемножаем числа. И тут есть проблема. Если с умножением всё более-менее хорошо, то как быть со сложением? Из-за того, что мы работаем только с одиночными двоичными цифрами, непонятно, как сложить 1 и 1, чтобы снова получилась одна двоичная цифра. Значит вместо классического сложения нужно использовать какое-то другое.
Введём операцию сложения как сложение по модулю 2 (хорошо известный программистам XOR):
Умножение будем выполнять как обычно. Эти операции на самом деле введены не абы как, а чтобы получилась система, которая в математике называется полем. Поле — это просто множество (в нашем случае из 0 и 1), на котором так определены сложение и умножение, чтобы основные алгебраические законы сохранялись. Например, чтобы основные идеи, касающиеся матриц и систем уравнений по-прежнему были верны. А вычитание и деление мы можем ввести как обратные операции.
Множество из двух элементов 
с операциями, введёнными так, как мы это сделали, называется полем Галуа GF(2). GF — это Galois field, а 2 — количество элементов.
У сложения есть несколько очень полезных свойств, которыми мы будем пользоваться в дальнейшем.
Это свойство прямо следует из определения.
А в этом можно убедиться, прибавив 
к обеим частям равенства. Это свойство, в частности означает, что мы можем переносить в уравнении слагаемые в другую сторону без смены знака.
Проверяем корректность
Вернёмся к коду с утроением.
Для начала просто решим задачу проверки, были ли вообще ошибки при передаче. Как видно, из самого кода, принятое сообщение будет кодовым словом только тогда, когда все три цифры равны между собой.
Пусть мы приняли вектор-строку из трёх цифр. (Стрелочки над векторами рисовать не будем, так как у нас почти всё — это вектора или матрицы.)
Математически равенство всех трёх цифр можно записать как систему:
Или, если воспользоваться свойствами сложения в GF(2), получаем
Или
В матричном виде эта система будет иметь вид
где
Транспонирование здесь нужно потому, что — это вектор-строка, а не вектор-столбец. Иначе мы не могли бы умножать его справа на матрицу.
Будем называть матрицу 
проверочной матрицей. Если полученное сообщение — это корректное кодовое слово (то есть, ошибки при передаче не было), то произведение проверочной матрицы на это сообщение будет равно нулевому вектору.
Умножение на матрицу — это гораздо более эффективно, чем поиск в таблице, но у нас на самом деле есть ещё одна таблица — это таблица кодирования. Попробуем от неё избавиться.
Кодирование
Итак, у нас есть система для проверки
Её решения — это кодовые слова. Собственно, мы систему и строили на основе кодовых слов. Попробуем теперь решить обратную задачу. По системе (или, что то же самое, по матрице ) найдём кодовые слова.
Правда, для нашей системы мы уже знаем ответ, поэтому, чтобы было интересно, возьмём другую матрицу:
Соответствующая система имеет вид:
Чтобы найти кодовые слова соответствующего кода нужно её решить.
В силу линейности сумма двух решений системы тоже будет решением системы. Это легко доказать. Если 
и 
— решения системы, то для их суммы верно
что означает, что она тоже — решение.
Поэтому если мы найдём все линейно независимые решения, то с их помощью можно получить вообще все решения системы. Для этого просто нужно найти их всевозможные суммы.
Выразим сперва все зависимые слагаемые. Их столько же, сколько и уравнений. Выражать надо так, чтобы справа были только независимые. Проще всего выразить 
.
Если бы нам не так повезло с системой, то нужно было бы складывая уравнения между собой получить такую систему, чтобы какие-то три переменные встречались по одному разу. Ну, или воспользоваться методом Гаусса. Для GF(2) он тоже работает.
Итак, получаем:
Чтобы получить все линейно независимые решения, приравниваем каждую из зависимых переменных к единице по очереди.
Всевозможные суммы этих независимых решений (а именно они и будут кодовыми векторами) можно получить так:
где 
равны либо нулю или единице. Так как таких коэффициентов два, то всего возможно 
сочетания.
Но посмотрите! Формула, которую мы только что получили — это же снова умножение матрицы на вектор.
Строчки здесь — линейно независимые решения, которые мы получили. Матрица 
называется порождающей. Теперь вместо того, чтобы сами составлять таблицу кодирования, мы можем получать кодовые слова простым умножением на матрицу:
Найдём кодовые слова для этого кода. (Не забываем, что длина исходных сообщений должна быть равна 2 — это количество найденных решений.)
Итак, у нас есть готовый код, обнаруживающий ошибки. Проверим его в деле. Пусть мы хотим отправить 01 и у нас произошла ошибка при передаче. Обнаружит ли её код?
А раз в результате не нулевой вектор, значит код заподозрил неладное. Провести его не удалось. Ура, код работает!
Для кода с утроением, кстати, порождающая матрица выглядит очень просто:
Подобные коды, которые можно порождать и проверять матрицей называются линейными (бывают и нелинейные), и они очень широко применяются на практике. Реализовать их довольно легко, так как тут требуется только умножение на константную матрицу.
Ошибка по синдрому
Ну хорошо, мы построили код обнаруживающий ошибки. Но мы же хотим их исправлять!
Для начала введём такое понятие, как вектор ошибки. Это вектор, на который отличается принятое сообщение от кодового слова. Пусть мы получили сообщение , а было отправлено кодовое слово 
. Тогда вектор ошибки по определению
Но в странном мире GF(2), где сложение и вычитание одинаковы, будут верны и соотношения:
В силу особенностей сложения, как читатель сам может легко убедиться, в векторе ошибки на позициях, где произошла ошибка будет единица, а на остальных ноль.
Как мы уже говорили раньше, если мы получили сообщение с ошибкой, то 
. Но ведь векторов, не равных нулю много! Быть может то, какой именно ненулевой вектор мы получили, подскажет нам характер ошибки?
Назовём результат умножения на проверочную матрицу синдромом:
И заметим следующее
Это означает, что для ошибки синдром будет таким же, как и для полученного сообщения.
Разложим все возможные сообщения, которые мы можем получить из канала связи, по кучкам в зависимости от синдрома. Тогда из последнего соотношения следует, что в каждой кучке будут вектора с одной и той же ошибкой. Причём вектор этой ошибки тоже будет в кучке. Вот только как его узнать?
А очень просто! Помните, мы говорили, что у нескольких ошибок вероятность ниже, чем у одной ошибки? Руководствуясь этим соображением, наиболее правдоподобным будет считать вектором ошибки тот вектор, у которого меньше всего единиц. Будем называть его лидером.
Давайте посмотрим, какие синдромы дают всевозможные 5-элементные векторы. Сразу сгруппируем их и подчеркнём лидеров — векторы с наименьшим числом единиц.
 |
|
|---|---|
|
 |
|
 |
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
 |
В принципе, для корректирования ошибки достаточно было бы хранить таблицу соответствия синдрома лидеру.
Обратите внимание, что в некоторых строчках два лидера. Это значит для для данного синдрома два паттерна ошибки равновероятны. Иными словами, код обнаружил две ошибки, но исправить их не может.
Лидеры для всех возможных одиночных ошибок находятся в отдельных строках, а значит код может исправить любую одиночную ошибку. Ну, что же… Попробуем в этом убедиться.
Вектор ошибки равен 
, а значит ошибка в третьем разряде. Как мы и загадали.
Ура, всё работает!
Что же дальше?
Чтобы попрактиковаться, попробуйте повторить рассуждения для разных проверочных матриц. Например, для кода с утроением.
Логическим продолжением изложенного был бы рассказ о циклических кодах — чрезвычайно интересном подклассе линейных кодов, обладающим замечательными свойствами. Но тогда, боюсь, статья уж очень бы разрослась.
Если вас заинтересовали подробности, то можете почитать замечательную книжку Аршинова и Садовского «Коды и математика». Там изложено гораздо больше, чем представлено в этой статье. Если интересует математика кодирования — то поищите «Теория и практика кодов, контролирующих ошибки» Блейхута. А вообще, материалов по этой теме довольно много.
Надеюсь, когда снова будет свободное время, напишу продолжение, в котором расскажу про циклические коды и покажу пример программы для кодирования и декодирования. Если, конечно, почтенной публике это интересно.
4. Циклические коды
4.1 Основные понятия
Циклическим кодом
называется линейный блоковый (n,k)-код, который характеризуется свойством
цикличности, т.е. сдвиг влево на один шаг любого разрешенного кодового слова
дает также разрешенное кодовое слово, принадлежащее этому же коду и у которого,
множество кодовых слов представляется совокупностью многочленов степени (n-1) и
менее, делящихся на некоторый многочлен g(x) степени r = n-k, являющийся
сомножителем двучлена xn+1.
Многочлен g(x) называется
порождающим.
Как следует из определения, в циклическом коде кодовые слова
представляются в виде многочленов 
где n — длина кода;
— коэффициенты из поля GF(q).
Если код построен над полем GF(2), то
коэффициенты принимают значения 0 или 1 и код называется двоичным.
Пример. Если кодовое слово циклического кода 
то соответствующий
ему многочлен 
Например, если код
построен над полем GF(q)=GF(23), которое является расширением GF(2)
по модулю неприводимого многочлена f(z)=z3+z+1, а элементы этого поля
имеют вид, представленный в таблице 3,
| 0 | 000 | 0 | a3 | 011 | Z+1 |
| a0 | 001 | 1 | a4 | 110 | Z2+Z |
| a1 | 010 | Z | a5 | 111 | Z2+Z+1 |
| a2 | 100 | Z2 | a6 | 101 | Z2+1 |
то
коэффициенты 
принимают значения
элементов этого поля и поэтому они сами отображаются в виде многочленов
следующего вида 
где m — степень многочлена, по которому получено расширение поля GF(2);
ai — коэффициенты, принимающие значение элементов GF(2), т.е. 0 и
1.
Такой код называется q-ным.
Длина циклического кода
называется примитивной и сам код называется примитивным, если его длина
n=qm-1 над GF(q).
Если длина кода меньше длины примитивного кода,
то код называется укороченным или непримитивным.
Как следует
из определения общее свойство кодовых слов циклического кода — это их делимость
без остатка на некоторый многочлен g(x), называемый порождающим.
Результатом деления двучлена xn+1 на многочлен g(x)
является проверочный многочлен h(x).
При декодировании
циклических кодов используются многочлен ошибок e(x) и синдромный многочлен
S(x).
Многочлен ошибок степени не более (n-1) определяется из выражения
где 
—
многочлены, отображающие соответственно принятое (с ошибкой) и переданное
кодовые слова.
Ненулевые коэффициенты в е(x) занимают позиции, которые
соответствуют ошибкам.
Пример.
Синдромный многочлен, используемый при декодировании циклического
кода, определяется как остаток от деления принятого кодового слова на
порождающий многочлен, т.е. 
или 
Следовательно, синдромный многочлен зависит непосредственно от многочлена
ошибок е(х).Это положение используется при построении таблицы
синдромов, применяемой в процессе декодирования. Эта таблица содержит список
многочленов ошибок (см. первый столбец стандартного расположения кода в разделе
2.4) и список соответствующих синдромов, определяемых из выражения 
(см.
таблицу 4).
| (x) | S(x) |
| 1 | Rg(x)[1] |
| X | Rg(x)[x] |
| X2 | Rg(x)[x2] |
| · | · |
| · | · |
| · | · |
| X+1 | Rg(x)[x+1] |
| X2+1 | Rg(x)[x2+1] |
| · | · |
| · | · |
| · | · |
В процессе
декодирования по принятому кодовому слову вычисляется синдром, затем в таблице
находится соответствующий многочлен е(х), суммирование которого с принятым
кодовым словом дает исправленное кодовое слово, т.е. 
Перечисленные
многочлены 
можно складывать,
умножать и делить, используя известные правила алгебры, но с приведением
результата по mod 2, а затем по mod xn+1, если степень результата
превышает степень (n-1).
Примеры.
Допустим,
что длина кода n=7, то результат приводим по mod x7+1.
При
построении и декодировании циклических кодов в результате деления многочленов
обычно необходимо иметь не частное, а остаток от деления.
Поэтому
рекомендуется более простой способ деления, используя не многочлены, а только
его коэффициенты (вариант 2 в примере).
- Пример.
- 1.
- 2.
4.2 Матричное задание кодов
Циклический
код может быть задан порождающей и проверочной матрицами. Для их построения
достаточно знать порождающий g(x) и проверочный h(x) многочлены.
Для несистематического циклического кода матрицы строятся
циклическим сдвигом порождающего и проверочного многочленов, т.е. путем их
умножения на x 
и 
При построении
матрицы H(n,k) старший коэффициент многочлена h(x) располагается
справа.
Пример. Для циклического (7,4)-кода с порождающим многочленом
g(x)=x3+x+1 матрицы G(n,k) и H(n,k) имеют вид:
где 
Для систематического циклического кода матрица G(n,k)
определяется из выражения 
где
Ik — единичная матрица;
Rk,r — прямоугольная
матрица.
Строки матрицы Rk,r определяются из выражений 
или 
где
ai(x) — значение i-той строки матрицы Ik;
i — номер
строки матрицы Rk,r.
Пример. Матрица G(n,k) для
(7,4)-кода на основе порождающего многочлена g(x)=x3+x+1, строится в
следующей последовательности 
или 
Определяется
R4,3, используя 
так как 
Аналогичным способом
определяется 
В результате получаем 
или 
Используя выражение
получим тот же результат.
Строки матрицы G(n,k) можно определить
непосредственно из выражения 
где 
Проверочная матрица в систематическом виде строится на основе
матрицы G(n,k), а именно: 
где
Ir — единичная матрица; 
— матрица из
G(n,k) в транспонированном виде.
Пример. Для (7,4)-кода
матрица H(n,k) будет иметь вид: 
Одна из основных
задач, стоящих перед разработчиками устройств защиты от ошибок при передаче
дискретных сообщений по каналам связи является выбор порождающего многочлена
g(x) для построения циклического кода, обеспечивающего требуемое минимальное
кодовое расстояние для гарантийного обнаружения и исправления t-кратных ошибок.
Существуют специальные таблицы по выбору g(x) в зависимости от предъявляемых
требований к корректирующим возможностям кода. Однако у каждого циклического
кода имеются свои особенности формирования g(x). Поэтому при изучении конкретных
циклических кодов будут рассматриваться соответствующие способы построения g(x).
4.3 Коды БЧХ
Одним из классов
циклических кодов, способных исправлять многократные ошибки, являются коды БЧХ.
Примитивным кодом БЧХ, исправляющим tu ошибок,
называется код длиной n=qm-1 над GF(q), для которого элементы 
являются
корнями порождающего многочлена.
Здесь a —
примитивный элемент GF(qm).
Порождающий многочлен
определяется из выражения 
где
f1(x),f2(x)…- минимальные многочлены корней g(x).
Число проверочных элементов кода БЧХ удовлетворяет соотношению 
Пример. Определить значение порождающего многочлена для построения
примитивного кода БЧХ над GF(2) длины 31, исправляющего двух кратные ошибки
(tu=2).
Исходя из определения кода БЧХ корнями многочлена g(x)
являются: 
, где a — примитивный элемент GF(qm)=GF(25).
Порождающий многочлен определяется из выражения 
где f1(x),
f2(x), f3(x), f4(x) — минимальные многочлены
корней соответственно 
.
Примечание.
Минимальный многочлен элемента b поля
GF(qm) определяется из выражения 
, где 
— наименьшее целое
число, при котором 
.
Значения
минимальных многочленов будут следующими: 
Так как f1(x)=
f2(x)= f4(x), то 
На
практике при определении значений порождающего многочлена пользуются специальной
таблицей минимальных многочленов (см. таблицу 8 приложения), и выражением для
порождающего многочлена 
При этом работа
осуществляется в следующей последовательности.
По заданной длине кода n и
кратности исправляемых ошибок tu определяют:
— из выражения
n=2m-1 значение параметра m, который является максимальной степенью
сомножителей g(x);
— из выражения j=2tu-1 максимальный порядок
минимального многочлена, входящего в число сомножителей g(x).
— пользуясь
таблицей минимальных многочленов, определяется выражение для g(x) в зависимости
от m и j. Для этого из колонки, соответствующей параметру m, выбираются
многочлены с порядками от 1 до j, которые в результате перемножения дают
значение g(x).
Примечание.
В выражении для g(x) содержаться минимальные
многочлены только для нечетных степеней a, так как
обычно соответствующие им минимальные многочлены четных степеней a имеют аналогичные выражения.
Например, минимальные
многочлены элементов 
соответствуют
минимальному многочлену элемента a1,
минимальные многочлены элементов 
соответствуют
минимальному многочлену a3 и т.п.
Пример. Определить значение порождающего многочлена для построения
примитивного кода БЧХ над GF(2) длины 31, обеспечивающего tu=3.
Определяем значения m и j. 
Из таблицы
минимальных многочленов в соответствии с m=5 и j=5 получаем 
Заданные исходные
данные: n и tu или k и tu для построения циклического кода
часто приводят к выбору завышенного значения m и как следствие этого к
неоправданному увеличению длины кода. Такое положение снижает эффективность
полученного кода, так как часть информационных разрядов вообще не используется.
Пример. Требуется построить циклический код, исправляющий двух
кратные ошибки, если длина информационной части кода k=40.
Согласно
выражению для примитивного кода n=2m-1, ближайшая длина кода равна
63, для которой m=6, а r=mtu=12. Следовательно, код будет иметь n=63,
k=51. Неиспользованных информационных разрядов будет 11(51-40).
Подобное
несоответствие в ряде случаев можно устранить, применяя непримитивный код БЧХ.
Непримитивным кодом БЧХ, исправляющим tu ошибок,
называется код длины n над GF(q), для которого элементы 
являются корнями
порождающего многочлена.
Здесь bi-непримитивный элемент GF(qm), а
длина кода n равна порядку элемента bi.
Примечание.
Порядком элемента bi
является наименьшее n, для которого 
.
Пример.
Порядок элемента b3 поля GF(26)
равен 21, так как 
.
Порождающий многочлен непримитивного кода БЧХ, по аналогии с
примитивным кодом, определяется из выражения 
— минимальные многочлены
элементов 
поля
GF(qm), которые являются корнями g(x); i — степень непримитивного
элемента b.
Пример. Определить значение g(x)
для построения непримитивного кода БЧХ над GF(2) длины n=20, исправляющего двух
кратные ошибки.
Из таблицы непримитивных элементов GF(2m) (см.
таблицу 7 приложения) выбираем поле, элемент b которого
имеет порядок больший, но близкий к заданному n.
Такими являются
GF(26) и b3, порядок которого
n=21.
Так как j=2tu-1=2(2-1=3, то выражение для g(x) будет иметь
вид 
где f3(x) и f9(x) — минимальные многочлены элементов
b3 и b9
поля GF(26).
Значения этих многочленов следующие: 
Выражения для
f3(x) и f9(x) можно определить из таблицы минимальных
многочленов, используя для этого параметр m выбранного поля GF(2m) и
порядковые номера сомножителей g(x).
Для рассмотренного примера m=6, а
порядковые номера равны 3 и 9. Поэтому 
.
4.4 Способы кодирования
Задача кодирования
заключается в формировании по информационным словам a(x) кодовых слов u(x) циклического (n,k)-кода, который по своей структуре
может быть несистематическим и систематическим.
Формирование
кодовых слов несистематического кода заключается в умножении многочлена a(x),
отображающего информационную последовательность длины k, на порождающий
многочлен, т.е. u(x)=a(x)(g(x). Формирование кодовых
слов систематического кода заключается в преобразовании информационной
последовательности a(x) в соответствии с выражением u(x)=a(x)·xr+r(x).
Проверочная последовательность r(x) определяется двумя способами:
при использовании «классического» способа кодирования 
;
при использовании
способа кодирования, рекомендованного МККТТ 
,
где
x(1)r-1 — единичный многочлен степени (r-1).
Указанные выше
математические операции выполняют кодеры несистематического и систематического
кодов.
4.5 Способы декодирования с обнаружением ошибок
Процедура декодирования
циклического кода с обнаружением ошибок, по аналогии с процессом кодирования,
использует два способа:
— при кодировании «классическим»
способом декодирование основано на использовании свойства делимости без остатка
кодового многочлена u(x) циклического (n,k)-кода на
порождающий многочлен g(x). Поэтому алгоритм декодирования включает в себя
деление принятого кодового слова, описываемого многочленом 
на g(x), вычисление и
анализ остатка r(x). Если r(x)=0, то принятое кодовое слово считается
неискаженным. Если r(x)№0, то принятое кодовое слово
стирается и формируется сигнал «ошибка».
— при кодировании
способом МККТТ декодирование основано на свойстве получения определенного
контрольного остатка R0(x) при делении принятого кодового многочлена
u(x) на порождающий многочлен. Поэтому, если полученный
при делении остаток 
, то принятое кодовое
слово считается неискаженным. Если остаток 
, то принятое кодовое
слово стирается и формируется сигнал «ошибка».
Значение контрольного остатка
определяется из выражения 
.
4.6 Способы декодирования с исправлением ошибок
и схемная реализация декодирующих устройств
и схемная реализация декодирующих устройств
Декодирование циклического
кода в режиме исправления ошибок можно осуществлять различными способами. Ниже
излагаются два способа, являющиеся наиболее простыми.
В
основу первого способа положено использование таблицы синдромов (декодирования),
в которой каждому многочлену или образцу ошибок ei(x), соответствует
определенный синдром Si(x), представляющий остаток от деления
принятого кодового слова 
и соответствующего ему
ei(x) на g(x). Процедура декодирования следующая. Принятое кодовое
слово делится на g(x),
определяется Si(x) и соответствующий ему многочлен ei(x),
а затем суммируется с
ei(x). В результате получаем исправленное кодовое слово, т.е. 
.
В состав декодера входят: вычислитель
синдрома (ВС), два регистра сдвига RG1 и RG2, постоянное запоминающее устройство
(ПЗУ), котороесодержит 
слова длины n,
соответствующие многочленам ошибок ei(x).
Принятое кодовое слово
поступает на вход вычислителя синдрома, где осуществляется деление его на g(x) и
формирование Si(x), и одновременно — на вход RG2, где
накапливается. Синдром Si(x) используется в качестве адреса, по
которому из ПЗУ в регистр RG1 записывается ei(x), соответствующий
синдрому Si(x). Перечисленные операции завершаются за n тактов. В
течение последующих n тактов происходит поэлементное суммирование содержимого
RG2 и RG1, т.е. операция , и исправление ошибок.
В основе второго способа исправления ошибок, позволяющего
значительно сократить объем используемых табличных синдромов и существенно
упростить схему декодера, лежат следующие положения:
1. Синдром
Si(x), соответствующий принятому кодовому слову равен остатку от
деления на g(x), а также остатку
от деления соответствующего многочлена ошибок ei(x) на g(x), т.е. 
.
2.
Если Si(x) соответствует и ei(x), то
x( Si(x) является синдромом, который соответствует 
и 
или 
.
3.
При исправлении ошибок используются синдромы образцов ошибок только с ненулевым
коэффициентом в старшем разряде.
Поэтому при реализации
этого способа множество всех образцов ошибок разбивается на классы
эквивалентности. Каждый класс представляет циклический сдвиг одного образца
ошибок, а синдром этого класса соответствует образцу ошибок с ненулевым старшим
разрядом. Если вычисленный синдром принадлежит одному из классов эквивалентности
образцов исправляемых ошибок, то старший символ кодового слова исправляется.
Затем принятое слово и синдром циклически сдвигается, а процесс нахождения в
предыдущей по старшинству позиции повторяется.
Для исправления ошибок,
принадлежащих данному классу эквивалентности, нужно произвести n циклических
сдвигов.
Простейшим является декодер Меггитта. В состав декодера
входят: вычислитель синдрома, осуществляющий деление кодового слова на g(x)
и формирование соответствующего синдрома; блок декодеров (ДК), который настроен
на синдромы всех образцов исправляемых ошибок с ненулевыми старшими разрядами;
регистр сдвига RG.
При поступлении на вход схемы кодового слова его
символы заполняют регистр RG, а в вычислителе формируется соответствующий
синдром Si(x). Вычисленный синдром сравнивается со всеми табличными
синдромами, заложенными в схему блока ДК, и в случае совпадения с одним из них
на его выходе формируется сигнал, который исправляет ошибочный символ,
находящийся в старшем разряде регистра. После этого содержимое вычислителя и RG
циклически сдвигается на один шаг. Этот сдвиг реализует операции 
и . Если
новый синдром совпадает с одним из табличных синдромов, то это означает, что
произошла ошибка во втором по старшинству символе кодового слова, который,
перейдя в старший разряд RG, исправляется. Затем производится новый циклический
сдвиг на одну позицию и новая проверка на совпадение синдромов. После повторения
этого процесса n раз в RG будет сформировано исправленное кодовое слово.
Введение обратной связи для RG не обязательно, так как в процессе исправления
ошибок символы кодового слова поступают на выход декодера.
Пример. Рассмотрим схему и работу декодера Меггитта
циклического (15,7)-кода, обеспечивающего исправление одиночных и двойных
ошибок, с g(x)=x8+ x7+ x6+ x4+1 (см.
рисунок 8).
Блок декодеров настраивается на 15 синдромов, которые
представлены в таблице 5 и соответствуют классам эквивалентности с образцами
ошибок в старшем разряде.
| № | е(х) | S(x) | № | е(х) | S(x) |
|---|---|---|---|---|---|
| 1 | x14 | x7+ x6+x5+ x3 |
9 | x14+ x6 | |
| 2 | x14+ x13 | x7+ x4+x3+ x2 |
10 | x14+ x5 | x7+ x6+x3 |
| 3 | x14+ x12 | x7+ x6+x4+ x |
11 | x14+ x4 | x7+ x6+x5+ x4+x3 |
| 4 | x14+ x11 | 12 | x14+ x3 | x7+ x6+x5 |
|
| 5 | x14+ x10 | 13 | x14+ x2 | x7+ x6+x5+ x3+x2 |
|
| 6 | x14+ x9 | 14 | x14+ x1 | x7+ x6+x5+ x3+x |
|
| 7 | x14+ x8 | 15 | x14+ x0 | x7+ x6+x5+ x3+0 |
|
| 8 | x14+ x7 |
Допустим, что
ошибки в 3 и 5 разрядах, т.е. им соответствует многочлен ошибки
e(x)=x12+x10.
При поступлении на вход декодера
искаженного кодового слова он заполняет регистр и в вычислителе формируется
синдром 
.
Блок декодеров не
реагирует на этот синдром.
Затем происходит сдвиг кодового слова в RG, а в
BC формируется новый синдром 
.
Блок декодеров и в
этом случае не срабатывает.
При следующем сдвиге кодового слова в RG первый
искаженный разряд занимает старшую позицию в RG, а в BC формируется синдром 
, от
которого срабатывает БДК. В результате исправляется первая ошибка.
Следующим
сдвиг приводит к формированию синдрома 
.
Этот синдром
соответствует многочлену ошибки e(x)=x13+x0, т.к. первый
искаженный разряд по обратной связи должен занять младшую позицию RG.
На
синдром S(13,0) блок декодеров не реагирует.
При следующем сдвиге
кодового слова в RG второй искаженный разряд занимает старшую позицию в RG, а в
BC формируется синдром 
, от которого срабатывает
БДК. В результате исправляется вторая ошибка в кодовом слове.
4.7 Коды Рида-Соломона (РС)
Коды РС
являются недвоичными циклическими кодами, символы кодовых слов которых берутся
из конечного поля GF(q). Здесь q степень некоторого простого числа, например
q=2m.
Допустим, что РС-код построен над GF(8), которое является
расширением поля GF(2) по модулю примитивного многочлена f(z)=z3+z+1.
В этом случае символы кодовых слов кода будут иметь значения, представленные в
таблице 6.
| 000 | 0 | 0 | 011 | z+1 | a3 |
| 001 | 1 | a0 | 110 | z2+z | a4 |
| 010 | z | a1 | 111 | z2+z+1 | a5 |
| 100 | z2 | a2 | 101 | z2+1 | a6 |
Кодовые слова РС-кода
отображаются в виде многочленов 
,
где N — длина кода;
Vi — q-ичные коэффициенты (символы кодовых слов), которые могут
принимать любое значение из GF(q).
Эти коэффициенты как это следует из
таблицы, также отображаются многочленами с двоичными коэффициентами 
. Коды РС являются максимальными, т.к. при длине кода N и
информационной последовательности k они обладают наибольшим кодовым расстоянием
d=N-k+1.
Порождающим многочленом g(x) РС-кода является делитель двучлена
xN+1 степени меньшей N с коэффициентами из GF(q) при условии, что
элементы 
этого поля являются
корнями g(x). Здесь 
— примитивный элемент
GF(q).
На основе этого определения, а также теоремы Безу,
выражение для порождающего многочлена РС-кода будет иметь вид 
.
Степень g(x) равна d-1=N-k=R.
В РС-кодах принадлежность кодовых слов
данному коду определяется выполнением d-1 уравнений в соответствии с выражением
(*),
где Vi — символы-коэффициенты из GF(q);
z0,
z1… zN-1 — ненулевые элементы GF(q).
Элементы
z0, z1… zN-1 называются локаторами, т.е.
указывающими на номер позиции символа кодового слова.
Например, указателем i
— позиции является локатор zi или элемент ai
GF(q).
Так как все локаторы должны быть различны и причем ненулевыми, то их
число в GF(q) равно q-1. Следовательно, такое количество символов должно быть в
кодовых словах кода.Поэтому обычно длина РС-кода определяется из
выражения N=q-1.
Пример. Допустим, что длина РС-кода равна N, кодовое
расстояние d=3, то в соответствии с (*) проверочными уравнениями будут 
Свойства РС-кодов.
1. Циклический сдвиг кодовых слов, символы которых принимают значение из
GF(q), порождает новые кодовые слова этого же кода.
2. Сумма по mod2 двух и
более кодовых слов дает кодовое слово, принадлежащее этому же коду.
3.
Кодовое расстояние РС-кода определяется не по двоичным элементам, а по q-ичным
символам.
4. В РС-коде, исправляющем tu ошибок порождающий
многочлен определяется из выражения 
. Обычно m0
принимают равным 1. Однако, с помощью разумного выбора значения m0,
иногда можно упростить схему кодера.
5. Корректирующие способности РС-кода
определяются его кодовым расстоянием. 
где T0 и
Tu — длина пакетов, в которых обнаруживаются и исправляются ошибки.
Обнаружение ошибок в кодовых словах состоит в проверке условий ((), т.е.
определении синдрома 
, элементы которого
определяются из выражения 
.
Пример. Требуется сформировать кодовое слово РС-кода над
GF(23), соответствующее двоичной информационной последовательности
a(1,0)=000000011100101.
Так как m=3, то каждый q-ичный символ кода состоит
из трех двоичных элементов. Поэтому с учетом таблицы 6 a(x)=a3x2+ a2x+a6.
Определяем параметры кода.
N=q-1=7; k=5; R=2; d=N-k+1=3; 
.
Кодовое слово формируется в соответствии с выражением. 
,
где
.
В
результате 
или в двоичной форме
V(1,0)=000.000.011.100.101.101.101.
Содержание
Раздел разработан в 2010 г. при поддержке компании RAIDIX
Циклические коды
Рассмотрим линейное пространство $ mathbb V^n $ двоичных кодов, т.е. упорядоченных наборов (строк) $ (x_1,dots,x_{n}) $ из $ n_{} $ чисел $ {x_1,dots,x_n}subset {0,1} $.
Рассмотрим непустое подмножество $ mathbb U $ пространства $ mathbb V^n $, обладающее следующим свойством: если строка $ (u_1,u_2,dots,u_n) $ принадлежит $ mathbb U $, то этому подмножеству принадлежит и строка, полученная из этой в результате циклического сдвига вправо:
$$ (u_n,u_1,u_2,dots,u_{n-1}) in mathbb U $$
т.е. все компоненты (разряды) вектора сдвигаются вправо на одну позицию, тот элемент, что при этом сдвиге «вываливается» за пределы строки, переставляется в ее начало.
Очевидно, что:
$$ (u_{n-1},u_n,u_1dots,u_{n-2}) in mathbb U , dots , (u_2,u_3,dots,u_{n-1},u_{1}) in mathbb U , $$
т.е. множество $ mathbb U $ должно содержать, по крайней мере, $ n_{} $ строк (которые, впрочем, не обязательно будут различными). Если, вдобавок, множество $ mathbb U $ является подпространством пространства $ mathbb V^n $, т.е. замкнуто относительно операции сложения строк по модулю $ 2_{} $, то такое множество называется циклическим кодом. Будем обозначать его буквой $ C_{} $.
Заметим, что циклический код можно определить и на основе циклического сдвига влево:
$$
begin{array}{c}
rightarrow \
begin{array}{c}
(u_1,u_2,u_3, u_4, u_5) \
(u_5,u_1, u_2, u_3, u_4) \
(u_4,u_5, u_1, u_2, u_3) \
(u_3,u_4, u_5, u_1, u_2) \
(u_2,u_3, u_4, u_5, u_1)
end{array}
end{array} qquad qquad
begin{array}{c}
leftarrow \
begin{array}{c}
(u_1,u_2, u_3, u_4, u_5) \
(u_2, u_3, u_4, u_5, u_1) \
(u_3, u_4, u_5, u_1, u_2) \
(u_4,u_5, u_1, u_2, u_3) \
(u_5,u_1, u_2, u_3, u_4)
end{array}
end{array}
$$
В самом деле, правый набор строк получается в результате перестановки строк левого набора.
Структура кода
Для прояснения идейных основ использования циклических кодов в зашумленных каналах связи рассмотрим сначала их прототип в $ mathbb Z^n $, т.е. в пространстве строк с целочисленными элементами.
С точки зрения традиционного для линейной алгебры определения, $ mathbb Z^n $ не является линейным пространством. Тем не менее если рассмотреть его как множество строк с целочисленными компонентами
$$ mathbb Z^n = left{ (x_1,dots,x_n) mid {x_j}_{j=1}^n subset mathbb Z right} $$
относительно операций покомпонентного сложения и умножения на целочисленные скаляры, то все аксиомы
1
—
8
линейного векторного пространства будут выполнены.
Рассмотрим строку $ (a_{0},a_{1},dots,a_{n-1}) in mathbb Z^n $. Она порождает следующую циклическую матрицу
$$
mathfrak C=left(begin{array}{lllll}
a_{0} & a_{1} & a_2 & dots & a_{n-1} \
a_{n-1} & a_{0} & a_{1} & dots & a_{n-2} \
a_{n-2} & a_{n-1} & a_{0} & dots & a_{n-3} \
vdots & & & & vdots \
a_{1} & a_{2} & a_{3} & dots & a_{0}
end{array}
right) .
$$
Тогда линейная оболочка строк этой матрицы
$$ mathcal L (mathfrak C^{[1]},mathfrak C^{[2]},dots, mathfrak C^{[n]}) $$
образует циклический код $ C_{} $. Чему равна размерность $ dim C $ этого подпространства ? Очевидно, это будет зависеть от вида строки
$ (a_{0},a_{1},dots,a_{n-1}) $. Так,
$$ . mbox{ при выборе } quad a_0=1,a_{1}=0,a_{2}=0,dots,a_{n-1}=0, quad mbox{ получим } dim C = n , $$
$$ . mbox{ при выборе } quad a_{0}=1,a_{1}=1,dots,a_{n-1}=1 quad mbox{ получим } dim C = 1 . $$
В общем же случае, вопрос можно переформулировать в терминах ранга матрицы $ {mathfrak C} $. Вычисление этого ранга проведем с использованием соображений из пункта
☞
ЦИКЛИЧЕСКАЯ МАТРИЦА.
Рассмотрим полином $ g(x)= a_{0}+ a_{1}x+ dots +a_{n-2}x^{n-2}+ a_{n-1}x^{n-1} $. Вычислим остаток $ g_1(x) $ от деления произведения $ xcdot g(x) $ на полином $ x^{n}-1 $:
$$ xcdot g(x) equiv a_{0}x+ a_{1}x^2+ dots + a_{n-2}x^{n-1}+ a_{n-1}x^{n} equiv
$$
$$
equiv a_{0}x+ a_{1}x^2+ dots + a_{n-2}x^{n-1}+a_{n-1}(x^{n}-1+1) equiv
$$
$$
equiv underbrace{a_{n-1}+a_{0}x+ a_{1}x^2+ dots + a_{n-2}x^{n-1}}_{g_{_1}(x)} + a_{n-1}(x^{n}-1) .
$$
Оказывается, что коэффициенты остатка даются второй строкой матрицы $ mathfrak C $. Далее по аналогии остаток от деления произведения $ x^2cdot g(x) $ на полином $ x^{n}-1 $ совпадает с остатком от деления $ xcdot g_1(x) $ на $ x^{n}-1 $ и коэффициенты этого остатка даются третьей строкой матрицы $ mathfrak C $.
Вывод: матрица $ mathfrak C_{} $ состоит из коэффициентов остатков деления полиномов $ {x^jg(x)}_{j=0}^{n-1} $
на $ x^{n}-1 $. Будем говорить, что полином $ g_{} (x) $ порождает циклический код $ C_{} $.
Оказывается, ранг матрицы $ mathfrak C_{} $ связан с наибольшим общим делителем полиномов $ g_{}(x) $ и $ x^{n}-1 $.
Т
Теорема 1. Если полином $ g_{}(x) $ порождает циклический код $ C_{} $, то
$$ operatorname{rank} ({mathfrak C} ) = n — deg operatorname{HOD}(g(x), x^n-1) ; $$
$$ det mathfrak C_{} = mathcal R(g(x), x^n-1) , $$
где в правой части последней формулы стоит результант.
Доказательство
☞
ЗДЕСЬ.
Как выяснить принадлежность заданной строки $ B= (b_{0},b_{1},dots,b_{n-1}) in mathbb Z^n $ циклическому коду $ C_{} $? В общем случае, для ответа на этот вопрос приходится вычислять ранг расширенной матрицы, полученной присоединением к матрице $ mathfrak C_{} $ данной строки1):
$$ tilde {mathfrak C} = left(begin{array}{c} mathfrak C \ B end{array} right) . $$
Т
Теорема 2. Имеем:
$$ B in C qquad iff qquad operatorname{rank} ({mathfrak C} ) = operatorname{rank} ( tilde {mathfrak C} ) . $$
П
Пример. Пусть $ n_{}=4 $ и циклический код $ C_{} $ порождается полиномом $ g(x)=-2+2,x-x^2+x^3 $. Имеем:
$$
mathfrak C=left(begin{array}{rrrr}
-2&2&-1&1\
1&-2&2&-1\
-1&1&-2&2\
2&-1&1&-2
end{array}
right)
$$
и $ operatorname{rank} ({mathfrak C} ) = 3 $ поскольку $ det {mathfrak C} =0 $, а
$$
left|
begin{array}{rrr}
-2&2&-1\
1&-2&2\
-1&1&-2
end{array}
right| ne 0 .
$$
Пусть теперь требуется установить значения параметра $ {color{Red} alpha } $, при которых строка
$ B= (-3,1,{color{Red} alpha },2) $ принадлежит циклическому коду $ C_{} $. Имеем, согласно теореме 2:
$$
B in C quad iff quad
operatorname{rank} left(begin{array}{rrrr}
-2&2&-1&1\
1&-2&2&-1\
-1&1&-2&2\
2&-1&1&-2 \
-3&1&{color{Red} alpha }& 2
end{array}
right)=3 quad iff
$$
$$
iff quad
left|begin{array}{rrrr}
-2&2&-1&1\
1&-2&2&-1\
-1&1&-2&2\
-3&1&{color{Red} alpha } & 2
end{array}
right|=0 quad iff quad {color{Red} alpha }=0 .
$$
♦
!
Попробуем теперь выбрать порождающий циклический код полином $ g(x) $ среди делителей полинома $ x^{n}-1 $.
Т
Теорема 3. Пусть порождающий полином
$$ g(x)=a_0+a_1x+dots+a_rx^rin mathbb Z[x], (0< r<n, a_rne 0) $$
кода $ C_{} $ является делителем полинома $ x^{n}-1 $. Тогда $ operatorname{rank} (mathfrak C_{} ) = n — r $. Строка $ (b_0,b_1,dots,b_{n-1}) $ принадлежит коду $ C_{} $ тогда и только тогда, когда полином $ b_0+b_1x+dots+b_{n-1}x^{n-1} $ делится на $ g(x) $.
Доказательство. Циклическая матрица имеет следующую структуру2):
$$
begin{array}{rl}
mathfrak C=
left(begin{array}{llllllll}
a_0 & a_1 & dots & a_r & 0 & dots & 0 & 0 \
& a_0 & dots & a_{r-1} & a_r & dots & 0 & 0 \
& & ddots & & & ddots & & \
& & & a_0 & a_1& dots & & a_r \
hline
a_r & 0 & dots & & a_0 & dots & & a_{r-1} \
a_{r-1} & a_r & dots & & & & & a_{r-2} \
vdots & & ddots & & & & ddots & vdots \
a_1 & a_2 & dots & a_r & & dots & & a_0
end{array}
right) &
begin{array}{l}
left.begin{array}{l}
\ \ \ \
end{array}right} n-r
\
begin{array}{l}
\ \ \ \
end{array}
end{array}
end{array}
$$
Поскольку $ operatorname{HOD}(g(x),x^n-1)equiv g(x) $, то, в соответствии с теоремой 1, $ operatorname{rank} ({mathfrak C} ) = n — r $. Легко видеть, что линейно независимыми строками матрицы являются первые $ n-r $ строк (над горизонтальной чертой). Строка $ B= (b_0,b_1,dots,b_{n-1}) $, принадлежащая коду $ C_{} $, должна линейно выражаться через эти строки:
$$ B=gamma_0 (a_0,a_1,dots,a_r,0,dots,0)+gamma_1 (0,a_0,a_1,dots,a_r,dots,0)+dots+gamma_{n-r-1}
(0,dots,0,a_0,dots,a_r) , $$
и это равенство может быть переписано как полиномиальное тождество:
$$b_0+b_1x+dots+b_{n-1}x^{n-1}equiv $$
$$
equiv gamma_0(a_0+a_1x+dots+a_rx^{r})+gamma_1(a_0x+a_1x^2+dots+a_rx^{r+1})+
$$
$$
+dots+gamma_{n-r-1}(a_0x^{n-r-1}+a_1x^{n-r}+dots+a_rx^{n-1}) equiv
$$
$$
equiv (gamma_0+gamma_1x+dots+gamma_{n-r-1}x^{n-r-1})(a_0+a_1x+dots+a_rx^{r}) .
$$
♦
=>
Обозначим через $ h_{}(x) $ частное от деления $ x^n-1 $ на $ g_{}(x) $. Строка $ (b_0,b_1,dots,b_{n-1}) $ принадлежит коду $ C_{} $ тогда и только тогда, когда
$$ (b_0+b_1x+dots+b_{n-1}x^{n-1})h(x) equiv 0 pmod{x^n-1} . $$
Доказательство. Если $ (b_0,b_1,dots,b_{n-1}) in C_{} $, то, в соответствии с теоремой,
полином $ G(x)= b_0+b_1x+dots+b_{n-1}x^{n-1} $ может быть представлен в виде произведения $ Q(x) g(x) $; тогда $ Q(x) g(x)h(x) equiv Q(x)(x^n-1) equiv 0 pmod{x^n-1} $.
С другой стороны, если $ G(x)h(x) equiv 0 pmod{x^n-1} $, то $ G(x)h(x) equiv tilde Q(x) (x^n-1) $ при $ tilde Q(x) in mathbb Z[x] $ и, следовательно, $ G(x) equiv tilde Q(x) g(x) $. Применение теоремы завершает доказательство.
♦
Полином $ h_{}(x) $, связанный с порождающим циклический код $ C_{} $ полиномом $ g_{}(x) $ тождеством
$$ h(x) g(x) equiv x^n-1 $$
называется проверочным полиномом циклического кода.
П
Пример. Пусть $ n_{}=6 $ и циклический код порождается полиномом $ g(x)=1+2,x+2,x^2+x^3 $.
Проверить принадлежность строки $ B=(-1,-1,1,3,3,1) $ данному коду.
Решение. Имеем:
$$ x^6-1equiv overbrace{(x^3+2,x^2+2,x+1)}^{=g(x)}overbrace{(x^3-2,x^2+2,x-1)}^{=h(x)} . $$
1.
Можно действовать по аналогии с предыдущим примером и вычислить $ operatorname{rank} (tilde {mathfrak C}) $.
2.
Можно, в соответствии с теоремой 3, составить полином $ G(x)=-1-x+x^2+3,x^3+3,x^4+x^5 $ и проверить его на делимость с порождающим код полиномом $ g_{}(x) $:
$$ G(x)equiv (x^2+x-1) g(x) . $$
3.
Можно проверить выполнение условия следствия к теореме 3:
$$ G(x)h(x) equiv x^8+x^7-x^6-x^2-x+1 equiv x^2+x-1-x^2-x+1 pmod{x^6-1} . $$
4.
Наконец, можно рассмотреть корни $ lambda_1=-1, lambda_2=-frac{1}{2}+mathbf i frac{sqrt{3}}{2}, lambda_3=-frac{1}{2}-mathbf i frac{sqrt{3}}{2} $ полинома $ g_{} (x) $ и проверить, что в каждом из них полином $ G_{}(x) $ обращается в нуль.
Последний способ кажется неконструктивным. В самом деле, он является очевидным следствием способа
2
и основной теоремы высшей алгебры. Я привожу его как «заготовку на будущее», которое грядёт
☟
НИЖЕ.
♦
Кодирование
В предыдущем пункте было проведено описание циклического кода $ C_{} $ как подмножества (линейного подпространства) пространства $ mathbb Z^n $. Теперь надо описать способы кодирования, т.е. сопоставления вектору информационных разрядов $ (x_1,dots,x_k) $ конкретного кодового слова
$ (b_0,b_1,dots,b_{n-1}) $ из $ C_{} $.
На практике используются два способа кодирования. Оба используют циклические коды с порождающим полиномом $ g(x)=a_0+a_1x+dots+a_{r-1}x^{r-1}+x^r $, который удовлетворяет двум условиям3):
1.
$ g_{}(x) $ является нетривиальным делителем полинома $ x^n-1 $;
2.
его степень $ r_{} $ связана с числом информационных разрядов $ k_{} $ равенством: $ k=n-r $.
Несистематическое кодирование заключается в сопоставлении информационному вектору $ (x_1,dots,x_k) $ кодового слова $ (b_0,b_1,dots,b_{n-1}) $ по правилу, которое описывается на языке полиномов:
$$ b_0+b_1x+dots+b_{n-1}x^{n-1}equiv (x_1+x_2x+dots+x_kx^{k-1}) g(x) , $$
т.е. заключается в умножении «информационного» полинома на полином, порождающий код.
Систематическое кодирование заключается в сопоставлении информационному вектору $ (x_1,dots,x_k) $ кодового слова $ (c_0,c_1,dots,c_{n-1}) $ по правилу:
$$ c_0+c_1x+dots+c_{n-1}x^{n-1}equiv (x_1+x_2x+dots+x_kx^{k-1}) x^{n-k} — R(x) , $$
где $ R(x) $ — остаток от деления полинома $ (x_1+x_2x+dots+x_kx^{k-1}) x^{n-k} $ на порождающий код полином $ g_{}(x) $.
На основании теоремы 3 из предыдущего ПУНКТА, можно утверждать, что оба способа кодирования корректны: полиномы $ b_0+b_1x+dots+b_{n-1}x^{n-1} $ и $ c_0+c_1x+dots+c_{n-1}x^{n-1} $ делятся на порождающий код полином $ g_{}(x) $, а значит, наборы их коэффициентов являются кодовыми словами.
Теперь проиллюстрируем оба этих способа на примере.
П
Пример. Пусть $ n_{}=6 $ и циклический код порождается полиномом $ g(x)=1+2,x+2,x^2+x^3 $. Найти кодовые слова, соответствующие информационному вектору $ (x_1,x_2,x_3) $.
Решение. Составляем полином $ M(x)= x_1+x_2x+x_3x^2 $.
В случае несистематического кодирования
$$ M(x)g(x)equiv x_1+(2,x_1+x_2)x+(2,x_1+2,x_2+x_3)x^2+(x_1+2,x_2+2,x_3)x^3+
(x_2+2,x_3)x^4+x_3x^5 , $$
т.е. кодовое слово имеет вид
$$ (x_1, 2,x_1+x_2, 2,x_1+2,x_2+x_3, x_1+2,x_2+2,x_3, x_2+2,x_3, x_3) . $$
Легко убедиться, что это слово является результатом умножения информационного вектора на верхнюю часть циклической матрицы $ mathfrak C $:
$$
(x_1,x_2,x_3)
left(begin{array}{cccccc}
1 & 2 & 2 & 1 & 0 & 0 \
0 & 1 & 2 & 2 & 1 & 0 \
0 & 0 & 1 & 2 & 2 & 1
end{array}
right) ;
$$
что, впрочем, вполне ожидаемо, если посмотреть доказательство теоремы 3 из предыдущего ПУНКТА: кодовое слово обязано быть линейной комбинацией строк циклической матрицы.
Для систематического кодирования вычисляем сначала остаток от деления $ M(x)x^3 $ на $ g_{}(x) $:
$$ R(x) equiv (-x_1+2,x_2-2,x_3)+(-2,x_1+3,x_2-2,x_3)x+(-2,x_1+2,x_2-x_3)x^2 ; $$
и кодовое слово имеет вид
$$ (x_1-2,x_2+2,x_3, 2,x_1-3,x_2+2,x_3, 2,x_1-2,x_2+x_3, x_1, x_2, x_3) . $$
Здесь тоже можно выписать матричное представление:
$$
(x_1,x_2,x_3)
left(begin{array}{rrrrrr}
1 & 2 & 2 & 1 & 0 & 0 \
-2 & -3 & -2 & 0 & 1 & 0 \
2 & 2 & 1 & 0 & 0 & 1
end{array}
right) .
$$
Матрица систематического кодирования может быть получена из матрицы несистематического кодирования с помощью элементарных преобразований над строками:
$$
left(begin{array}{cccccc}
1 & 2 & 2 & 1 & 0 & 0 \
0 & 1 & 2 & 2 & 1 & 0 \
0 & 0 & 1 & 2 & 2 & 1
end{array}
right)quad
rightarrow quad
left(begin{array}{rrrrrr}
1 & 2 & 2 & 1 & 0 & 0 \
-2 & -3 & -2 & 0 & 1 & 0 \
0 & 0 & 1 & 2 & 2 & 1
end{array}
right)
quad
rightarrow quad
left(begin{array}{rrrrrr}
1 & 2 & 2 & 1 & 0 & 0 \
-2 & -3 & -2 & 0 & 1 & 0 \
-2 & -4 & -3 & 0 & 2 & 1
end{array}
right)
quad
rightarrow
$$
$$
rightarrow quad
left(begin{array}{rrrrrr}
1 & 2 & 2 & 1 & 0 & 0 \
-2 & -3 & -2 & 0 & 1 & 0 \
2 & 2 & 1 & 0 & 0 & 1
end{array}
right) ;
$$
и этот факт достаточно ожидаем, поскольку два способа кодирования соответствуют разным выборам кодовых слов (базисных строк) в одном и том же линейном подпространстве пространства $ mathbb Z^n $ — циклическом коде $ C_{} $. Какую информацию содержат строки этой матрицы — какие полиномы они порождают? — Оказывается, эти строки состоят из коэффициентов полиномов вида
$$ x^{j}-(b_{j,r-1}x^{r-1}+b_{j,r-2}x^{r-2}+dots+b_{j1}x^1+b_{j0}) quad npu quad jin{r,dots,n-1} , $$
где полином в скобках является остатком от деления $ x^{j} $ на порождающий код полином $ g_{}(x) $.
$$ x^3 equiv -1-2,x-2,x^2, x^4 equiv 2+3,x+2,x^2, x^5 equiv -2-2,x-x^2 pmod{1+2,x+2,x^2+x^3} . $$
♦
Вывод. Несистематический способ кодирования проще в реализации; систематический — удобнее с точки зрения расположения в кодовом слове информационных и проверочных разрядов — они объединены в блоки.
В одном из последующих ПУНКТОВ будет сменена на противоположную нумерация разрядов кодового слова; в сравнении с используемой до сих пор, мы будем записывать коэффициенты полиномов по убыванию степеней $ x_{} $. Тогда при систематическом способе кодирования информационные разряды займут привычные для теории кодирования места в начале кодового слова.
Свёртка
Исследование операции умножения полиномов по модулю $ x^{n}-1 $, использованной в
☝
ВЫШЕ требует отдельного пункта. Впрочем, при первом чтении этот материал можно пропустить.
Предположим, что заданы два полинома
$$ f(x)=a_0+a_1x+dots+a_{n-1}x^{n-1} qquad mbox{ и } qquad g(x)=b_0+b_1x+dots+b_{n-1}x^{n-1} $$
с целыми коэффициентами. Организуем их умножение по модулю полинома $ x^n-1 $, действуя по схеме, которую проиллюстрируем для случая $ n_{}=5 $:
$$ (a_0+a_1x+a_2x^2+a_3x^3+a_4x^4)(b_0+b_1x+b_2x^2+b_3x^3+b_4x^4) = $$
$$
=
begin{array}{l|rrrrr|rrrr}
b_0times & a_0&+a_1x&+a_2x^2 &+a_3x^3 &+a_4x^4 & + & & &\
b_1times & & a_0x&+a_1x^2 &+a_2x^3 &+a_3x^4 &+a_4x^5 &+ & &\
b_2times & & & a_0x^2 & +a_1x^3 & +a_2x^4& +a_3x^5&+a_4x^6 & + &\
b_3times & & & & a_0x^3 & +a_1x^4 & +a_2x^5&+a_3x^6&+a_4x^7& + \
b_4times & & & & & a_0x^4 & +a_1x^5& +a_2x^6&+a_3x^7&+a_4x^8
end{array}
$$
Использование соотношений $ x^5 equiv 1, x^6 equiv x, x^7 equiv x^2, x^8 equiv x^3 pmod{x^5-1} $ позволяет циклически перебросить слагаемые, стоящие справа от правой черты влево от нее:
$$
equiv
begin{array}{l|lllll}
b_0times & a_0&+a_1x&+a_2x^2 &+a_3x^3 &+a_4x^4 + \
b_1times & a_4&+ a_0x&+a_1x^2 &+a_2x^3 &+a_3x^4 + \
b_2times & a_3&+ a_4x& +a_0x^2 & +a_1x^3 & +a_2x^4+ \
b_3times & a_2&+ a_3x& +a_4x^2 &+a_0x^3 & +a_1x^4 + \
b_4times & a_1&+ a_2x&+a_3x^2&+a_4x^3 & +a_0x^4
end{array} pmod{x^5-1} .
$$
Дальше остается только собрать подобные члены. Результатом такого умножения полиномов будет полином
$ c_0+c_1x+c_2x^2+c_3x^3+c_4x^4 $ с коэффициентами, задаваемыми соотношениями:
$$
begin{array}{llllll}
c_0=&a_0b_0&+a_1b_4&+a_2b_3&+a_3b_2&+a_4b_1 \
c_1=&a_0b_1&+a_1b_0&+a_2b_4&+a_3b_3&+a_4b_2 \
c_2=&a_0b_2&+a_1b_1&+a_2b_0&+a_3b_4&+a_4b_3 \
c_3=&a_0b_3&+a_1b_2&+a_2b_1&+a_3b_0&+a_4b_4 \
c_4=&a_0b_4&+a_1b_3&+a_2b_2&+a_3b_1&+a_4b_0
end{array}
$$
Здесь коэффициенты $ a_0,a_1,a_2,a_3,a_4 $ расположены в «естественном» порядке, а их сомножители — коэффициенты $ b_4,b_3,b_2,b_1,b_0 $ — при подъеме с последней формулы вверх циклически сдвигаются влево. Эту цикличность можно «заложить» в индексы если воспользоваться модулярным формализмом:
$$ c_0=sum_{j=0}^4 a_jb_{5-j pmod{5}}, c_1=sum_{j=0}^4 a_jb_{6-j pmod{5}},
c_2=sum_{j=0}^4 a_jb_{7-j pmod{5}}, c_3=sum_{j=0}^4 a_jb_{8-j pmod{5}}, c_4=sum_{j=0}^4 a_jb_{9-j pmod{5}} ;
$$
как принято
☞
ЗДЕСЬ, $ n pmod{5} $ означает остаток от деления натурального числа $ n_{} $ на $ 5_{} $.
Циклическая свёртка
Для произвольных векторов-строк $ X=(x_{1},dots,x_n) $ и $ Y=(y_{1},dots,y_n) $ вектор $ Z=(z_{1},dots,z_n) $,
с элементами, определяемыми формулами
$$ z_k=sum_{j=1}^n x_jy_{n+k-j pmod{n}}= $$
$$
begin{array}{lcl}
=x_1y_k+x_2y_{k-1}+dots+x_ky_1 & + & \
& + & x_{k+1}y_n+x_{k+2}y_{n-1}+dots+x_ny_{k+1}
end{array}
$$
при $ k in {1,dots,n} $, называется циклической свёрткой векторов $ X_{} $ и $ Y_{} $, сама операция нахождения свертки обозначается $ ast $:
$$ Z=Xast Y .$$
Аналогичное определение используется и для полиномов. Если $ f(x)=a_0+a_{1}x+dots+a_{n-1}x^{n-1} $ и $ g(x)=b_0+b_1x+dots+b_{n-1}x^{n-1} $, то
$$ c_0+c_1x+dots+c_{n-1}x^{n-1}=f(x)cdot g(x) pmod{x^n-1} qquad iff $$
$$ iff qquad (c_0,c_1,dots,c_{n-1})= (a_0,a_1,dots,a_{n-1})ast (b_0,b_1,dots,b_{n-1}) . $$
Мы не вводили формальных ограничений на то, чтобы старшие коэффициенты полиномов $ f_{} $ и $ g_{} $ были отличны от нуля. Если применить определение к полиномам, степени которых удовлетворяют неравенству $ deg f+ deg g < n $, то результатом циклической свертки оказывается произведение полиномов $ f_{}(x) $ и $ g_{}(x) $ — в традиционном смысле, а не по какому-либо модулю!
Задача. Организовать экономное вычисление циклической свёртки.
Решение этой задачи см. в разделе
☞
УМНОЖЕНИЕ ПОЛИНОМОВ.
Исправление ошибок…
Снова рассматриваем циклические коды в $ mathbb Z^n $. В соответствии с определением, принадлежность кодового слова $ (b_0,b_1,dots,b_{n-1}) $ циклическому коду $ C_{} $, порождаемому полиномом $ g(x)=a_0+a_1x+a_2x^2+dots+a_{r}x^{r}, (r<n,a_{r}ne 0) $, равносильна тому, что полином $ G(x)=b_0+b_1x+b_2x^2+dots+b_{n-1}x^{n-1} $ делится на $ g_{}(x) $. Предположим теперь, что при передаче по зашумленному каналу связи кодовое слово исказилось и на выходе мы получили вектор
$ (tilde b_0,tilde b_1,dots,tilde b_{n-1}) $. Этот вектор задает некоторый полином $ tilde G(x)= tilde b_0+ tilde b_1x+ tilde b_2x^2+dots+ tilde b_{n-1}x^{n-1} $.
В дальнейшем, для простоты, будем говорить о передаваемых по каналу полиномах, имея в виду строки их коэффициентов; кроме того, будем нумеровать разряды строк $ (tilde b_0,tilde b_1,dots,tilde b_{n-1}) $, начиная с нулевого.
…анализом остатков
Полином $ s_{}(x) $, равный остатку от деления полинома $ tilde G(x) $ на порождающий циклический код полином $ g_{}(x) $, называется синдромом полинома $ tilde G(x) $ в данном коде:
$$ s(x)={bf mbox{СИНДРОМ }}(tilde G(x)) = tilde G(x) pmod{g(x)} . $$
Если синдром $ s_{}(x) $ полученного на выходе из канала полинома $ tilde G(x) $ тождественно равен $ 0_{} $, то будем считать, что ошибка передачи не обнаружена.
П
Пример. Пусть $ n=6 $ и циклический код порождается полиномом
$$ g(x)=1+2,x+2,x^2+x^3 , . $$
Пусть при передаче по каналу кодового полинома $ G(x)=-1-x+x^2+3,x^3+3,x^4+x^5 $ произошла ошибка ровно в одном из коэффициентов. Вычислим синдромы получающихся полиномов $ tilde G(x) $.
Пусть сначала «испортился» старший коэффициент и мы получили на выходе полином
$$ tilde G(x)=-1-x+x^2+3,x^3+3,x^4+alpha, x^5 qquad npu quad alpha in mathbb Z . $$
Имеем:
$$ {bf mbox{СИНДРОМ }}(tilde G(x))equiv (2-2,alpha)+(2-2,alpha),x+(1-alpha),x^2 ; $$
т.е. получился полином $ 2_{} $-й степени, в котором пока трудно увидеть намек на какую-то идею. Вычислим теперь синдром от полинома $ xtilde G(x) $:
$$ {bf mbox{СИНДРОМ }}(xtilde G(x))equiv alpha — 1 ; $$
и вот этот полином — вместо ожидаемой $ 2_{} $-й степени — имеет нулевую степень, т.е. равен константе. Более того, эта константа обращается в нуль как раз при том единственном значении параметра $ alpha_{} $, которое обеспечивает совпадение полинома $ tilde G(x) $ с кодовым полиномом $ G_{}(x) $!
Пойдем дальше:
$$ {bf mbox{СИНДРОМ }}(x^2tilde G(x))equiv (alpha — 1)x ; $$
т.е. синдром получается домножением предыдущего на $ x_{} $. Аналогично:
$$ {bf mbox{СИНДРОМ }}(x^3tilde G(x))equiv (alpha — 1)x^2 , $$
и т.д.
Попробуем теперь испортить в кодовом полиноме $ G_{}(x) $ коэффициент при $ x^{4} $:
$$ tilde G(x)=-1-x+x^2+3,x^3+beta,x^4+x^5 qquad npu quad beta in mathbb Z . $$
Снова последовательно вычисляем синдромы для последовательности $ G_{}(x),xG_{}(x),x^2G_{}(x),dots $:
$$
begin{array}{lcl}
{bf mbox{СИНДРОМ }}(tilde G(x))&equiv& (2,beta-6) +(3beta-9)x+(2beta-6)x^2, \
{bf mbox{СИНДРОМ }}(xtilde G(x))&equiv& (6-2beta)+(6-2beta)x+ (3-beta)x^2,\
{bf mbox{СИНДРОМ }}(x^2tilde G(x))&equiv&beta- 3, \
{bf mbox{СИНДРОМ }}(x^3tilde G(x))&equiv&(beta- 3)x,\
{bf mbox{СИНДРОМ }}(x^4tilde G(x))&equiv&(beta- 3)x^2,\
dots & & dots \
end{array}
$$
Видим проявление того же эффекта, что и в предыдущем случае: при каком-то показателе $ j_{} $ синдром полинома $ x^j tilde G(x) $ становится равным константе, причем эта константа обращается в нуль только при значении параметра, обеспечивающем выполнение тождества $ tilde G(x)equiv G(x) $.
Проверим наблюдение для случая «порчи» других коэффициентов. Оформим результаты в виде таблицы:
верхняя ее строка показывает при каком мономе полинома
$$ G(x)=-1-x+x^2+3,x^3+3,x^4+x^5 $$
портится коэффициент, а сама таблица содержит степени синдромов полиномов $ x^j tilde G(x) $
$$
begin{array}{r|cccccc}
& x^5 & x^4 & x^3 & x^2 & x & x^{0} \
hline
\
tilde G & 2 & 2 & 2 & 2 & 1 & 0 \
xtilde G & 0 & 2 & 2 & 2 & 2 & 1 \
x^2tilde G & 1 & 0 & 2 & 2 & 2 & 2 \
x^3tilde G & 2 & 1 & 0 & 2 & 2 & 2 \
x^4tilde G & 2 & 2 & 1 & 0 & 2 & 2 \
x^5tilde G & 2 & 2 & 2 & 1 & 0 & 2 \
x^6tilde G & 2 & 2 & 2 & 2 & 1 & 0
end{array}
$$
Видим, что в последовательности синдромов обязательно встречается константа и встречается она при значении показателя $ j_{} $, устойчиво связанного с номером разряда кодового слова (или индекса коэффициента полинома), в котором происходит ошибка. Более того, подтверждается и другое наблюдение: эта константа обращается в нуль только при условии когда ошибки при передаче кодового слова по каналу не происходит.
♦
Т
Теорема 1. Пусть порождающий циклический код полином $ g_{}(x) $ является нетривиальным делителем полинома $ x^{n}-1 $. Если при передаче кодового полинома $ G_{}(x) $ по каналу связи произошла ровно одна ошибка в $ j_{} $-м коэффициенте и получен полином $ tilde G(x)=G(x)+E x^j $, то
$$ {bf mbox{СИНДРОМ }}(x^{n-j}tilde G(x))equiv E . $$
Доказательство. Имеем:
$$ x^{n-j}tilde G(x) equiv x^{n-j} G(x)+E x^n equiv E pmod{g(x)} , $$
поскольку $ G_{}(x) $ делится на $ g_{}(x) $ и $ x^n-1 $ делится на $ g_{}(x) $.
Итак, ошибка обнаружена. Теперь осталось показать, что остальные синдромы — «нормальные», т.е. отличные от константы, и, следовательно, ошибка обнаружена однозначно. В общем случае это утверждение неверно. Так, к примеру, при
$$ n=12, g=x^6-1, tilde G(x)=underbrace{1+x-x^3+x^4-x^5-x^6-x^7+x^9-x^{10}+x^{11}}_{=G(x)}+E,x^5 $$
получим, что
$$ {bf mbox{СИНДРОМ }}(xtilde G(x))equiv {bf mbox{СИНДРОМ }}(x^7tilde G(x))equiv E , $$
т.е. наряду с возможностью декодирования в истинный полином $ G_{}(x) $ , обнаруживается еще и «фантом» — полином
$$ G_{E}(x)= 1+x-x^3+x^4+(E-1)x^5-x^6-x^7+x^9-x^{10}+(1-E)x^{11} , $$
являющийся кодовым при любом значении $ E in mathbb Z $.
Тем не менее, можно утверждать, что, как правило, такой ситуации не возникнет. Не будем пока строго обосновывать этот вывод, а покажем, что всегда возможно выбрать порождающий полином $ g_{}(x) $ так, чтобы не возникло указанного в предыдущем абзаце эффекта. Итак, фактически надо гарантировать, чтобы сравнение
$$
x^{ell} equiv gamma pmod{g(x)}
$$
при $ gamma in mathbb Z $ не выполнялось ни при одном показателе $ ellin {1,2,dots,n-1} $.
С этой целью, выберем в качестве $ g_{}(x) $ полином $ g(x)equiv (x-1)X_{n}(x) $, где $ X_n(x) $ — полином из пункта
☞
УРАВНЕНИЕ ДЕЛЕНИЯ КРУГА, корнями которого являются все первообразные корни $ n_{} $-й степени из единицы (и только такие корни). Таким образом, $ r=deg g=phi(n)+1 $, где $ phi $ — функция Эйлера. Обозначим $ lambda_1=1,lambda_2,dots,lambda_r $ — корни $ g_{}(x) $. Тогда требуемое сравнение эквивалентно полиномиальному тождеству
$$ iff x^{ell} equiv g(x)Q_k(x)+ gamma quad npu quad Q_k(x)in mathbb Z[x] . $$
При подстановке в него корней $ lambda_{j} $ получаем:
$$ 1=gamma, lambda_2^{ell}=gamma,dots,lambda_r^{ell}=gamma , $$
откуда $ lambda_2^{ell}=1 $ и это равенство невозможно при $ ellin {1,2,dots,n-1} $ поскольку его выполнение противоречило бы первообразности корня $ lambda_{2} $.
♦
Мы пока умышленно не касаемся реальных способов выбора порождающего полинома кода, а только постепенно сужаем область его выбора формулированием естественных ограничений, возникающих из практики его использования.
Алгоритм. Последовательно строим синдромы полиномов $ tilde G, xtilde G,x^2 tilde G,dots, x^{n-1} tilde G $ до тех пор, пока не встретим полином нулевой степени (константу): $ {bf mbox{СИНДРОМ }}(x^{n-j}tilde G(x))=E $; заключаем, что в соответствующем моному $ x^{j} $ разряде кодового слова произошла ошибка; вычитаем эту константу из соответствующего разряда полученного слова:
$$ (b_0,b_1,dots,b_{j-1},tilde b_j-E,dots,b_{n-1}) $$
и получим истинное кодовое слово.
Последовательное вычисление синдромов организуется достаточно просто с учетом следующего утверждения.
Т
Теорема 2. Если
$$ s(x)=s_0+s_1x+dots+s_{r-1}x^{r-1} $$
— синдром полинома $ F(x) in mathbb Z[x] $, а $ tilde s(x)=tilde s_0+tilde s_1x+dots+ tilde s_{r-1}x^{r-1} $ — синдром полинома $ xF(x) $, то коэффициенты $ tilde s_j $ вычисляются по правилу:
$$ tilde s_0=-s_{r-1}a_0, tilde s_1=s_0-s_{r-1}a_1, tilde s_2=s_1-s_{r-1}a_2,dots,
tilde s_{r-1}=s_{r-2}-s_{r-1}a_{r-1} .
$$
Для исправления единичной ошибки можно также использовать проверочный полином $ h_{}(x) $ кода. В самом деле, факт ошибки устанавливается проверкой $ tilde G(x) h(x) notequiv 0 pmod{x^n-1} $.
Т
Теорема 3. Если $ tilde G(x)equiv G(x)+E x^j $, то
$$ tilde G(x) h(x) equiv E, x^j h(x) pmod{x^n-1} , $$
т.е. место ошибки устанавливается по совпадению остатка от деления $ tilde G(x) h(x) $ на $ x^n-1 $ с циклическим сдвигом строки коэффициентов полинома $ h_{}(x) $.
Можно развить предложенный подход к коррекции ошибок, основанный на проверке степеней синдромов последовательности $ {x^{ell} tilde G(x) }_{ell=0}^{n-1} $, на случай появления нескольких ошибок.
П
Пример. Пусть $ n=12 $ и циклический код порождается полиномом $ g(x)= 1-x+2,x^2-x^3+x^4 $. Пусть при передаче по каналу кодового полинома
$$ G(x)=1-4,x+4,x^2-x^3-5,x^4+11,x^5-13,x^6+14,x^7-10,x^8+9,x^9-
$$
$$ -5,x^{10}+3,x^{11} $$
произошли ошибки в двух коэффициентах. Вычислим синдромы получающихся полиномов $ tilde G(x) $.
Пусть сначала испорчены два старших коэффициента:
$$ tilde G(x)=1-4,x+4,x^2-x^3-5,x^4+11,x^5-13,x^6+14,x^7-10,x^8+9,x^9+
$$
$$
+beta x^{10}+alpha x^{11} quad npu quad {alpha,beta} subset mathbb Z .
$$
Получаем:
$$
{bf mbox{СИНДРОМ }}(tilde G(x))equiv (alpha-beta-8)+(1-2alpha-beta)x+(alpha-3)x^2+(-2-beta-alpha)x^3 ;
$$
и степень синдрома «не внушает подозрений» — она равна ожидаемой степени остатка от деления произвольного полинома на $ g_{}(x) $. Далее,
$$
{bf mbox{СИНДРОМ }}(xtilde G(x))equiv (alpha+beta+2)+(-2beta-10)x+(beta+5)x^2+(-beta-5)x^3 ,
$$
и снова не подозрений нет. Но вот следующий синдром
$$
{bf mbox{СИНДРОМ }}(x^2tilde G(x))equiv (beta+5)+(alpha-3)x
$$
имеет степень меньшую $ 3_{} $, более того, обращение в нуль его коэффициентов позволяет установить исходный (кодовый) полином $ G_{}(x) $. Формально:
$$ G(x) equiv tilde G(x) — x^{12-2}times {bf mbox{СИНДРОМ }}(x^2tilde G(x)) .$$
Проверим гипотезу на другом примере. Пусть
$$ tilde G(x)=1-4,x+4,x^2-x^3-5,x^4+11,x^5+delta,x^6+gamma,x^7-10,x^8+9,x^9-5,x^{10}+3,x^{11}
quad npu quad {gamma,delta} subset mathbb Z .
$$
Опустим вычисления, приведя только оценки степеней синдромов
$$
begin{array}{c|c|c|c|c|c|c|c}
j & 0 & 1 & 2 & 3 & 4 & 5 & 6 \
hline
&&&&&&& \
deg {bf mbox{СИНДРОМ }}(x^jtilde G(x)) & 3 & 3 & 3 & 3 & 3 & 3 & 1
end{array}
$$
при
$$
{bf mbox{СИНДРОМ }}(x^6tilde G(x))equiv (delta+13)+(gamma-14),x .
$$
Снова понижение степени синдрома свидетельствует об обнаружении ошибки, снова коэффициенты подсказывают величины этих ошибок:
$$ G(x) equiv tilde G(x) — x^{12-6}times {bf mbox{СИНДРОМ }}(x^6tilde G(x)) .$$
Испортим теперь два коэффициента «вразбивку»:
$$ tilde G(x)=1-4,x+4,x^2-x^3+zeta x^4+11,x^5+eta,x^6+14,x^7-10,x^8+9,x^9-5,x^{10}+3,x^{11}
quad npu quad {zeta,eta} subset mathbb Z .
$$
$$
begin{array}{c|c|c|c|c|c|c|c|c|c}
j & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \
hline
&&&&&&&& \
deg {bf mbox{СИНДРОМ }}(x^jtilde G(x)) & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2
end{array}
$$
при
$$
{bf mbox{СИНДРОМ }}(x^8tilde G(x))equiv (zeta+5)+(eta+13)x^2 .
$$
Исправление возможно:
$$ G(x) equiv tilde G(x) — x^{12-8}times {bf mbox{СИНДРОМ }}(x^8tilde G(x)) .$$
Однако если ошибочные коэффициенты оказываются разнесенными по полиному $ tilde G $ немного больше, как, к примеру, в
$$ tilde G(x)=1-4,x+4,x^2-x^3-5,x^4+theta x^5-13,x^6+14,x^7+xi,x^8+9,x^9-5,x^{10}+3,x^{11} ,
$$
то оценки степеней синдромов последовательности $ {x^{ell} tilde G(x) }_{ell=0}^{11} $ не позволят определить местоположение ошибок, поскольку все они имеют степень $ 3_{} $. Хотя наблюдательный читатель — с помощью интуиции — выделит в последовательности этих синдромов один, отличающийся по внешнему виду от остальных, именно —
$$
{bf mbox{СИНДРОМ }}(x^7tilde G(x))equiv (theta-11)+(10+xi),x^3 ,
$$
и убедится, что кодовый полином получится по формуле, которую вывели выше:
$$ G(x) equiv tilde G(x) — x^{12-7}times {bf mbox{СИНДРОМ }}(x^7tilde G(x)) ;$$
но эту человеческую бдительность трудно реализовать программно…
♦
Возникает подозрение, что обнаруженный эффект понижения степени синдрома сработает и в общем случае:
$$ tilde G(x)=G(x)+x^j E(x) $$
при $ deg E< r=deg g $, т.е. в случае, когда при передаче по каналу ошибки происходят серией4) в (не более чем) $ deg E(x) $ подряд идущих разрядах. Действительно, при таком ограничении на степень полинома $ E(x) $ имеем:
$$ {bf mbox{СИНДРОМ }}(x^{n-j} tilde G(x)) equiv E(x) , $$
т.е. «поврежденный кусок» при проверке не пропустим. Если же, вдобавок, $ deg E(x) $ много меньше $ r_{} $, то «место повреждения» — число $ j_{} $ — будем производить по принципу максимального правдоподобия, полагая
$$ j=min_{ellin{0,1,dots,n-1}} deg {bf mbox{СИНДРОМ }}(x^{n-ell} tilde G(x)) ; $$
иными словами, выбирая из последовательности синдромов те, что имеют минимальную степень.
Можно сходу придумать контрпример к предлагаемой схеме.
П
Пример. Пусть
$$ n=18, g(x)= 1+x+x^2-x^3-x^4-x^5+x^6+x^7+x^8 ,$$
и полученный полином имеет вид:
$$ tilde G(x)= 10+4,x+8,x^2-15,x^3-9,x^4-12,x^5+12,x^6+13,x^7+18,x^8+8,x^9
$$
$$
-8,x^{11}-11,x^{12}-5,x^{13}+4,x^{14}+9,x^{15}+9,x^{16}+2,x^{17} . $$
Подобрать кодовый полином $ G_{}(x) $, «породивший» $ tilde G(x) $.
Решение. Последовательным вычислением синдромов полиномов $ x^{n-ell} tilde G(x) $ обнаружим полиномы минимальной степени
$$ x^6tilde G(x)equiv 2-x^3 qquad u qquad x^{12}tilde G(x)equiv -1+2,x^3 . $$
Таким образом, кодовыми полиномами, выбираемыми по критерию минимализации степени синдрома оказываются два:
$$
G_1(x)equiv tilde G(x) — (-2,x^{12}+x^{15}) qquad u qquad G_2(x)equiv tilde G(x)-(x^6-2,x^9) .
$$
♦
Однако нельзя слишком уж сильно портить линейный код: понятие кодового расстояния не зря вводилось… 
…анализом с помощью корней порождающего полинома
Вернемся к случаю одиночной ошибки, описанному в теореме $ 1_{} $ предыдущего пункта. Пусть
$ tilde G(x) equiv G(x)+E x^j $, где $ Ein mathbb Z $ и $ G_{}(x) $ — кодовый полином. Последнее означает, что $ G_{}(x) $ делится нацело на полином $ g_{}(x) $, порождающий циклический код: $ G_{}(x) equiv Q(x)g(x) $ при $ Q(x)in mathbb Z[x] $.
Рассмотрим какой-то из корней полинома $ g_{}(x) $; поскольку $ g_{}(x) $ договорились выбирать среди делителей полинома $ x^n -1 $, то этот корень — это корень $ n_{} $-й степени из $ 1_{} $ и, в общем случае, комплексное число. Обозначим его $ varepsilon_{} $. Подстановка $ x=varepsilon_{} $ в кодовый полином $ G_{}(x) $ даст $ 0_{} $, а в полином $ tilde G(x) $ — величину
$$ tilde G(varepsilon_{}) = G(varepsilon)+E varepsilon_{}^j = E varepsilon_{}^j . $$
Можно было бы назвать эту величину синдромом полинома $ tilde G(x) $ поскольку ее отличие от нуля свидетельствует о наличии ошибки при передаче по каналу связи, но мы пока не будем вводить новых определений.
Таким образом, место ошибки (т.е. поврежденного коэффициента = разряда кодового слова) обнаруживается по совпадению числа
$ tilde G(varepsilon_{}) $ с элементом последовательности
$$ E varepsilon_{}^0, E varepsilon_{}^1, E varepsilon_{}^2,dots, E varepsilon_{}^{n-1} . $$
При дополнительном условии, что в этой последовательности не будет одинаковых элементов (или коллизий).
Последнее замечание накладывает дополнительное ограничение на выбор полинома $ g_{} $. Выберем его так, чтобы среди его корней находился хотя бы один первообразный корень степени n из единицы. Для определенности, пусть это будет корень
$$ varepsilon_1= cos frac{2 pi}{n} + mathbf i sin frac{2 pi}{n} . $$
Тогда, по теореме из пункта
☞
КОРНИ ИЗ ЕДИНИЦЫ, все элементы последовательности $ { varepsilon_1^k }_{k=0}^{n-1} $ будут различными и представление комплексного числа $ tilde G(varepsilon_1) $ в тригонометрической форме:
$$ tilde G(varepsilon_1) = rho left( cos varphi + mathbf i sin varphi right) quad npu quad
varphiin [0,2, pi [ ,
$$
позволит однозначно определить место ошибки $ j_{} $ и ее величину $ E_{} $ по формулам:
$$ E= rho,quad 2pi k/n= varphi . $$
В предложенной схеме есть один изъян, который проиллюстрируем на примере.
П
Пример. Пусть
$$ n=6, g(x)=-1+2,x-2,x^2+x^3 , ;. $$
Корнем $ g_{}(x) $ является
$ varepsilon_1=frac{1}{2}+ mathbf i frac{sqrt{3}}{2} $ — первообразный корень $ 6_{} $-й степени из единицы.
Пусть при передаче кодового полинома $ G(x)=3-5,x+2,x^2+3,x^3-5,x^4+2,x^5 $ произошла одна ошибка и на выходе из канала получен полином $ tilde G(x)equiv G(x)-3,x^2 $. Подставляем в него $ x=varepsilon_1 $:
$$ tilde G(varepsilon_1)=frac{3}{2}(1-mathbf i sqrt{3}) $$
и начинаем сравнивать полученное выражение со степенями $ varepsilon_1^k $:
$$ { varepsilon_1^k }_{k=0}^{5}=1, frac{1}{2}(1+mathbf i sqrt{3}), frac{1}{2}(-1+mathbf i sqrt{3}), -1, frac{1}{2}(-1-mathbf i sqrt{3}), frac{1}{2}(1-mathbf i sqrt{3}) .
$$
Видим, что возможны два варианта:
$$ tilde G(varepsilon_1)=- 3 varepsilon_1^2=3 varepsilon_1^5 . $$
Эта неоднозначность возникла вследствие того, что в предложенной выше схеме мы ошибочно предположили величину $ E_{} $ положительной.
♦
Для ликвидации изъяна схемы, будем выбирать $ n_{} $ нечетным. Тогда множество $ { varepsilon_1^k }_{k=0}^{n-1} $ теряет симметрию относительно начала координат и ошибку будем обнаруживать проверкой условия ee вещественности5):
$$ tilde G(varepsilon_1)/varepsilon_1^k in mathbb R quad iff quad tilde G(varepsilon_1)varepsilon_1^{n-k} in mathbb R . $$
(Последнее соотношение следует из равенства $ varepsilon_1^k varepsilon_1^{n-k}= varepsilon_1^{n}=1 $.)
П
Пример. Пусть
$$ n=15, g(x)=1-x+x^3-x^4+x^5-x^7+x^8 $$
Корнем $ g_{}(x) $ является
$$ varepsilon_1= frac{1}{8}left(1+sqrt{5}+sqrt{30-6sqrt{5}}+mathbf ileft[-sqrt{10-2,sqrt{5}}+sqrt{3}+sqrt{15}right]right)approx 0.913545+ 0.406737 , mathbf i $$
— первообразный корень $ 15_{} $-й степени из единицы.
Пусть при передаче кодового полинома
$$
G(x)=-2+6,x-5,x^2+x^3+x^4-5,x^5+10,x^6-6,x^7-2,x^8+5,x^9-6,x^{10}+7,x^{11}-2,x^{12}-3,x^{13}+2,x^{14}
$$
произошла одна ошибка и на выходе из канала получен полином $ tilde G(x)equiv G(x)-2,x^4 $. Домножаем $ tilde G(varepsilon_1) $ на степени $ varepsilon_1 $ и проверяем полученные выражения на вещественность6):
$$ tilde G(varepsilon_1)approx 0.209057-1.989044, mathbf i, tilde G(varepsilon_1)varepsilon_1= 1- sqrt{3} , mathbf i, tilde G(varepsilon_1)varepsilon_1^2approx 1.956295+0.415823 , mathbf i, dots, tilde G(varepsilon_1)varepsilon_1^{11}=-2, dots $$
Здесь ошибка обнаруживается однозначно.
♦
Можно ли развить этот подход до метода исправления двух (и более) ошибок? Попробуем это сделать для случая ошибок, возникших в двух соседних коэффициентах. Если это — младшие коэффициенты полинома:
$$ tilde G(x)equiv G(x)+E_0+E_1x , $$
то при $ r=deg g>2 $ линейный полином $ E_0+E_1x $ представляет собой остаток от деления $ tilde G(x) $ на порождащий код полином $ g_{}(x) $: поскольку $ G_{}(x) $ — кодовый полином, то
$ G(x) equiv Q(x) g(x) $ при $ Q(x)in mathbb Z $, но тогда тождество
$$ tilde G(x)equiv Q(x) g(x)+E_0+E_1x $$
фактически является определением остатка и частного от деления $ tilde G(x) $ на $ g_{}(x) $.
Если мы знаем выражения для хотя бы двух корней $ lambda_{1} $ и $ lambda_{2} $ полинома $ g_{}(x) $, то мы сможем установить коэффициенты $ E_0+E_1x $ из системы линейных уравнений:
$$ tilde G(lambda_1)=E_0+E_1 lambda_1, tilde G(lambda_2)=E_0+E_1 lambda_2 . $$
Схема понятна, и очевидным образом обобщается на случай, если полином $ tilde G(x) $ содержит больше двух ошибок, но они сконцентрированы в младших $ r-1 $ коэффициентах этого полинома — в этом случае, фактически, задача превращается в задачу полиномиальной интерполяции. Но вот общую ситуацию, когда расположение двух подряд идущих ошибок, т.е. число $ j_{} $ в
$$ tilde G(x)equiv G(x)+E_jx^j+E_{j+1}x^{j+1} $$
неизвестно, предложенный подход не покроет — например, в случае $ j+1 ge r $. Альтернативой может служить следующий алгоритм, который мы изложим в слегка упрощенном варианте, выбрав в качестве порождающего полинома $ g_{}(x) $ полином, имеющий корнем наряду с $ varepsilon_1 $ (первообразным корнем степени $ n_{} $ из единицы) еще и $ 1_{} $. Подстановка этих двух корней в последнее тождество даст систему уравнений:
$$ tilde G(1)=E_j+E_{j+1},quad tilde G(varepsilon_1)=varepsilon_1^j(E_j+E_{j+1}varepsilon_1) . $$
Домножим второе равенство на $ varepsilon_1^{n-j} $:
$$ tilde G(1)=E_j+E_{j+1},quad varepsilon_1^{n-j}tilde G(varepsilon_1)=E_j+E_{j+1}varepsilon_1 . $$
Из этих уравнений получим выражения для $ E_j $ и $ E_{j+1} $:
$$ E_j=-varepsilon_1frac{varepsilon_1^{n-j-1}tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1},quad
E_{j+1}=frac{varepsilon_1^{n-j}tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1}
.
$$
Ключевым обстоятельством является вещественность обоих чисел. Именно на этом построим критерий поиска «места ошибки», т.е. величины $ j_{} $: будем последовательно по $ kin {0,1,2,dots,n-2} $ вычислять величины
$$
-varepsilon_1frac{varepsilon_1^{k-1}tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1}quad u quad
frac{varepsilon_1^{k}tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1}
$$
до тех пор, пока оба числа не станут вещественными.
П
Пример. Пусть
$$ n=15, g(x)=(1-x+x^3-x^4+x^5-x^7+x^8)(x-1) , ,$$
т.е. полином $ g(x) $ получается домножением полинома из предыдущего примера на $ x_{}-1 $.
Пусть при передаче кодового полинома
$$
G(x)=2-8,x+11,x^2-6,x^3+8,x^5-17,x^6+14,x^7-9,x^9+11,x^{10}-11,x^{11}+5,x^{12}+3,x^{13}-3,x^{14}
$$
произошли две ошибки подряд и на выходе из канала получен полином $ tilde G(x)equiv G(x)-2,x^5+x^6 $.
Подстановка $ x_{}=1 $ в полученный полином дает $ tilde G(1)=-1 ne 0 $, т.е. наличие ошибки подтверждено. Далее, начинаем параллельное вычисление двух последовательностей:
$$ tilde G(varepsilon_1), tilde G(varepsilon_1)varepsilon_1,
tilde G(varepsilon_1)varepsilon_1^2,dots
$$
и
$$
frac{tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1}, frac{varepsilon_1tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1}, frac{varepsilon_1^{2}tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1}, dots ,
$$
где величина $ varepsilon_{1} $ — такая же, как и в предыдущем примере. Первая из этих последовательностей была рассмотрена в предыдущем случае — одиночной ошибки передачи. Вещественность какого-то элемента этой последовательности означает наличие ошибки в соответствующем коэффициенте полученного полинома. Таким образом, алгоритм содержит в себе еще и проверку гипотезы на одиночность ошибки. Если очередной элемент этой последовательности не является вещественным числом, произведем — с его помощью — вычисление соответствующего элемента второй последовательности. Если этот элемент — вещественное число, — а так и происходит в рассматриваемом примере на $ 10_{} $-м шаге:
$$
frac{varepsilon_1^{10}tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1} approx 1 ,
$$
то для контроля вычисляем еще и величину7)
$$
-varepsilon_1frac{varepsilon_1^{9}tilde G(varepsilon_1)-tilde G(1)}{varepsilon_1-1} approx -2 ,
$$
которая также оказывается вещественным числом. Место двух подряд идущих ошибок обнаружено. Их исправление производится по формуле $ tilde G(x)+ x^{15-10}(-2+x) $.
♦
Остался нерассмотренным общий случай — когда две ошибки не обязательно соседствуют:
$$ tilde G(x)equiv G(x)+E_jx^j+E_{k}x^{k} mbox{ при } j<k , . $$
Рассмотрение этого случая
☞
ЗДЕСЬ, но для понимания последующего материала настоящего раздела вполне достаточно уже разобранных выше случаев.
Двоичные коды
По ходу изложения существенно используются материалы из разделов
☞
ПОЛЯ ГАЛУА и
☞
КОД ХЭММИНГА.
Наша задача состоит в том, чтобы развитые в предыдущих пунктах идеи перевести на язык двоичных кодов — перейти к арифметике по модулю $ 2_{} $.
Циклический код образует линейное подпространство пространства $ mathbb V^n $ и, следовательно, является частным случаем линейного кода. Но тогда можно установить соответствие между способами их определения.
С целью состыковки обозначений принятым в литературе, изменим порядок записи разрядов циклического кода. Будем считать, что строке $ (b_{n-1},b_{n-2},dots,b_1,b_0) in mathbb V^n $ соответствует полином $ b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+dots+b_1x+b_0 $, т.е. младшие разряды строки соответствуют старшим коэффициентам полинома.
Пусть
$$ g(x)=x^r+a_{r-1}x^{r-1}+dots+a_0 quad npu quad {a_0,dots,a_{r-1}} subset {0,1} ,$$
— порождающий полином кода; мы выбираем его среди нетривиальных делителей по модулю $ 2_{} $ полинома $ x^n — 1 $. Проверочный полином $ h_{}(x) $ удовлетворяет теперь сравнению
$$ g(x)h(x) equiv 1 pmod{2} . $$
Циклический код $ C_{} $, порожденный полиномом $ g_{}(x) $, имеет базисными строки, составленные из коэффициентов полиномов $ x^{k-1}g(x),x^{k-2}g(x), dots,g(x) $. Иными словами, порождающей матрицей кода $ C_{} $ будет матрица
$$
begin{array}{rl}
& x^{n-1} x^{n-2} x^{n-3} dots x^k x^{k-1} dots 1 \
& downarrow downarrow downarrow quad quad quad downarrow downarrow qquad qquad downarrow \
mathbf G_{ktimes n}=&left(
begin{array}{ccccccccc}
1 & a_{r-1} & a_{r-2} & dots & a_1 & a_0 & 0 & dots & 0 \
& 1 & a_{r-1} & dots & a_2 & a_1 & a_0 & & 0 \
mathbb O & & ddots & & & & & ddots & vdots \
& & & 1 & dots & & & & a_0
end{array}
right)
end{array} .
$$
Эта матрица соответствует несистематическому способу кодирования.
В теории кодирования матрицу именно такого вида называют циклической — она представляет собой «верхнюю часть» квадратной циклической матрицы $ mathfrak C $ из
☝
ПУНКТА.
Базисные строки кода, а, значит, и порождающую матрицу, можно выбрать не единственным способом; так, систематическому способу кодирования соответствует порождающая матрица
$$mathbf G=left(
begin{array}{ccccc|lll}
1 & 0 & 0 & dots & 0 & b_{n-1,r-1} & dots & b_{n-1,0} \
& 1 & 0 & dots & 0 & b_{n-2,r-1} & dots & b_{n-2,0} \
mathbb O & & ddots & & vdots & vdots & & vdots \
& & & & 1 & b_{r,r-1} & dots & b_{r0}
end{array}
right) ,
$$
которая уже не является циклической. Справа от черты стоят коэффициенты остатков от деления мономов $ x^{n-1},x^{n-2},dots,x^r $ на $ g_{}(x) $:
$$ x^jequiv b_{j,r-1}x^{r-1}+b_{j,r-2}x^{r-2}+dots+b_{j0} equiv — (b_{j,r-1}x^{r-1}+b_{j,r-2}x^{r-2}+dots+b_{j0}) quad (operatorname{modd} 2,g(x)) . $$
Посмотрим что представляют собой проверочные матрицы соответствующие двум видам порождающей матрицы. Для последней матрицы она строится просто — поскольку она имеет блочную структуру вида
$ mathbf G = left[ E_k mid P right] $ при $ E_{k} $ — единичной матрице $ k_{} $-го порядка, то, в соответствии со следствием к теореме 1 из
☝
ПУНКТА, — проверочная матрица имеет вид $ mathbf H=left[ P^{top} mid E_{r} right] $
П
Пример. Пусть $ n=7, g(x)=x^3+x^2+1 $. Тогда для систематического кодирования
$$
mathbf G=
left(begin{array}{cccc|ccc}
1 & 0 & 0 & 0 & 1 & 1 & 0 \
0 & 1 & 0 & 0 & 0 & 1 & 1 \
0 & 0 & 1 & 0 & 1 & 1 & 1 \
0 & 0 & 0 & 1 & 1 & 0 & 1
end{array}
right) quad Rightarrow quad
mathbf H=
left(begin{array}{cccc|ccc}
1 & 0 & 1 & 1 & 1 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 1 & 0 \
0 & 1 & 1 & 1 & 0 & 0 & 1
end{array}
right) .
$$
Что представляют собой строки проверочной матрицы $ mathbf H $? — Оказывается, они содержат коэффициенты проверочного полинома $ h_{}(x) $ кода $ C_{} $. Действительно, в данном примере
$ h(x)=x^4+x^3+x^2+1 $ и
$$
begin{array}{ll}
begin{array}{c}
1 x x^2 x^3 x^4 x^5 x^6
end{array} & \
begin{array}{cccccccc}
downarrow & downarrow & downarrow & downarrow & downarrow & downarrow & downarrow &
end{array} & \
left(begin{array}{ccccccc}
1 & 0 & 1 & 1 & 1 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 1 & 0 \
0 & 1 & 1 & 1 & 0 & 0 & 1
end{array}
right)
&
begin{array}{l}
leftarrow h(x) \
leftarrow x^5+x^2+x+1equiv h(x)x^5 pmod{x^7-1} \
leftarrow x^6+x^3+x^2+xequiv h(x)x^6 pmod{x^7-1}
end{array}
end{array}
$$
Для несистематического кодирования структура проверочной матрицы оказывается еще более простой:
$$
mathbf G=
left(begin{array}{ccccccc}
1 & 1 & 0 & 1 & 0 & 0 & 0 \
0 & 1 & 1 & 0 & 1 & 0 & 0 \
0 & 0 & 1 & 1 & 0 & 1 & 0 \
0 & 0 & 0 & 1 & 1 & 0 & 1
end{array}
right) Rightarrow
$$
$$
Rightarrow
mathbf H=
left(
begin{array}{ccccccc}
0 & 0 & 1 & 0 & 1 & 1 & 1 \
0 & 1 & 0 & 1 & 1 & 1 & 0 \
1 & 0 & 1 & 1 & 1 & 0 & 0
end{array}
right)
begin{array}{l}
leftarrow h(x) \
leftarrow h(x)x \
leftarrow h(x)x^2
end{array}
,
$$
т.е. можно сказать, что $ mathbf H $ тоже является циклической матрицей с порождающим полиномом $ h_{}(x) $ — если записать этот полином «в обратном порядке» (т.е. формально рассмотреть полином $ h^{*}(x)equiv x^4h(1/x) $) и циклически переставить строки.
♦
Теперь обсудим разобранные в предыдущих пунктах способы обнаружения и исправления ошибок.
П
Пример. Рассмотрим циклический код из предыдущего примера: $ n=7, g(x)=x^3+x^2+1 $. Пусть при передаче кодового полинома $ G(x)=x^6+x^3+x+1 $ по каналу связи произошла ровно одна ошибка и на выходе получили полином $ tilde G(x)=x^6+x^4+x^3+x+1 $.
1-й cпособ.
Вычисление синдромов $ x^jtilde G(x) $ как остатков от деления на полином $ g_{}(x) $ — только теперь все вычисления идут по модулю $ 2_{} $:
$$ {bf mbox{СИНДРОМ }} (tilde G(x))equiv x^2+x+1 , $$
и, поскольку синдром ненулевой, то ошибка при передаче действительно произошла. Далее, последовательно вычисляем остатки от деления полиномов $ {bf mbox{СИНДРОМ }}(x^jtilde G(x)) $ при $ jin {1,2,dots } $
и при этих вычислениях можем воспользоваться теоремой 2 из
☝
ПУНКТА:
$$ {bf mbox{СИНДРОМ }}(xtilde G(x))equiv x+1 , {bf mbox{СИНДРОМ }}(x^2tilde G(x))equiv x(x+1)=x^2+1,
$$
$$ {bf mbox{СИНДРОМ }}(x^3tilde G(x))equiv x(x^2+1) pmod{g(x)} equiv 1 . $$
Остаток оказался равным константе, следовательно ошибочный коэффициент найден, и $ G(x) equiv tilde G(x) + x^{7-3} pmod{2} $.
2-й cпособ.
Домножение $ tilde G(x) $ на проверочный полином — использование теоремы 3 из
☝
ПУНКТА. Здесь $ h(x)=x^4+x^3+x^2+1 $ и
$$ tilde G(x) h(x) equiv x^6+x^4+x+1 equiv x^4h(x) equiv x quad (operatorname{modd} 2,x^7-1) . $$
Снова ошибочный коэффициент обнаружен.
3-й cпособ.
Подстановка в $ tilde G(x) $ корня порождающего полинома. А какого, собственно, корня? Если в случае предыдущего
☝
ПУНКТА, когда мы рассматривали коды в $ mathbb Z^n $, мы спокойно подставляли корень $ n_{} $-й степени из единицы, то для данного примера этот прием не пройдет — полином $ g_{}(x) $ не является делителем полинома $ x^7-1 $ во множестве $ mathbb Z_{} $, а только по модулю $ 2_{} $. Комплексные корни у полинома $ g_{} (x) $, разумеется, имеются, но они не являются корнями полинома $ x^7-1 $!
Рассматриваем поле Галуа $ mathbf{GF}(2^3) $. Поле содержит $ 8_{} $ элементов — полиномов вида
$ A_2x^2+A_1x+A_0 $ с коэффициентами из $ {0,1} $. Полином $ g(x)=x^3+x^2+1 $ является неприводимым по модулю $ 2_{} $ полиномом и, следовательно, операция умножения полиномов из поля по двойному модулю $ 2, g(x) $ удовлетворяет всем аксиомам поля. Полиномы $ x_{}, x^2, x^4 $ удовлетворяют уравнению $ g(mathfrak x)=0 quad (operatorname{modd} 2,g(x)) $ и являются примитивными элементами поля.
Последнее означает, что любой ненулевой элемент поля совпадает с какой-то степенью любого из этих полиномов, например:
$$
begin{array}{l|rrr||}
x^0 & & & 1 \
x^1 & & x & \
x^2 & x^2 & & \
x^3 & x^2 & &+1 \
x^4 & x^2 &+x &+1 \
x^5 & & x &+1 \
x^6 & x^2 &+x &
end{array}
qquad
begin{array}{|l|rrr}
(x^2)^0 & & & 1 \
(x^2)^1 & x^2 & & \
(x^2)^2 & x^2 & +x &+1 \
(x^2)^3 & x^2 &+x & \
(x^2)^4 & &x & \
(x^2)^5 & x^2 & &+1 \
(x^2)^6 & &x &+1
end{array}
$$
Эти полиномы и будут аналогами первообразных корней из
☝
ПУНКТА. Подставим любой из них в полином $ tilde G(mathfrak x) $ и проведем вычисления по двойному модулю. Например,
$$ tilde G(x) = x^6+x^4+x^3+x+1 equiv x^2+x+1 quad (operatorname{modd} 2,g(x)) $$
В приведенной выше таблице полином $ x^2+x+1 $ соответствует элементу $ x^4 quad (operatorname{modd} 2,g(x)) $. Это и есть моном полинома, в котором допущена ошибка.
Проверим, на всякий случай, наше заключение: не изменится ли оно если возьмем в качестве примитивного элемента полином $ x^{2} $?
$$ tilde G(x^2) = x^{12}+x^8+x^6+x^2+1 equiv x equiv (x^2)^4 quad (operatorname{modd} 2,g(x)) , $$
т.е. снова имеем $ 4 $-ю степень примитивного элемента поля.
♦
Итак, для целей корректировки ошибок порождающий циклический код полином $ g_{}(x) $ имеет смысл выбрать среди примитивных — тогда любой его корень можно использовать для исправления одной ошибки.
Теперь сделаем выжимку из всего предшествующего материала, оформив последовательно накладываемые на порождающий код полином ограничения в виде схемы:
Надо оправдать последний вывод. Циклический код является линейным кодом, у него имеется проверочная матрица $ mathbf H $. В предыдущем примере эта матрица как раз строилась для случая, когда степень полинома $ g_{}(x) $ равнялась $ 7=2^3-1 $. Столбцами этой $ 3times 7 $-матрицы были все трехбитные ненулевые столбцы — но тогда, с точностью до их перестановки, эта матрица совпадает с
проверочной матрицей (7,4)-кода Хэмминга.
Покажем теперь справедливость этого утверждения для общего случая $ n=2^M-1 $. Выбираем в качестве порождающего код полинома произвольный примитивный полином $ g_{}(x) $ степени $ M_{} $. Если $ mathfrak A in mathbf{GF}(2^M) $ — его корень, то этот корень будет примитивным элементом поля $ mathbf{GF}(2^M) $, построенного на основе операции умножения по двойному модулю $ 2,g(x) $. Примитивность корня означает, что все его степени
$$ mathfrak A^{n-1}, mathfrak A^{n-2},dots ,mathfrak A, mathfrak A^0=1 $$
будут различными элементами этого поля. Любой кодовый полином $ G(x)=b_0x^{n-1}+b_1x^{n-2}+dots+b_{n-1} in C $ делится на $ g_{}(x) $, и, следовательно (см. начало
☞
ПУНКТА ):
$$ G(mathfrak A)= b_0mathfrak A^{n-1}+b_1mathfrak A^{n-2}+dots+b_{n-1} =mathfrak o .$$
Любую степень $ mathfrak A^k $ элемента поля можно линейно выразить через первые $ M-1 $ степеней посредством соотношения $ g(mathfrak A)= mathfrak o $. Так, для приведенного выше примера:
$$
begin{array}{c}
n=7, g(x)=x^3+x^2+1 \
hline \
begin{array}{l|rrr|r}
mathfrak A^0 & & & 1 & 001\
mathfrak A^1 & & mathfrak A & & 010 \
mathfrak A^2 & mathfrak A^2 & & & 100 \
mathfrak A^3 & mathfrak A^2 & &+1 & 101 \
mathfrak A^4 & mathfrak A^2 &+mathfrak A &+1 & 111 \
mathfrak A^5 & & mathfrak A &+1 & 011 \
mathfrak A^6 & mathfrak A^2 &+mathfrak A & & 110
end{array}
end{array}
$$
и
$$
begin{array}{rrrrl}
G(mathfrak A)= b_0 (& mathfrak A^2 & +mathfrak A & )+ \
+ b_1 (& & mathfrak A &+1 ) + \
+ b_2 (& mathfrak A^2 &+mathfrak A &+1 ) + \
+ b_3 (& mathfrak A^2 & &+1 ) + \
+b_4 (& mathfrak A^2 & & ) + \
+b_5 (& &mathfrak A & ) + \
+b_6 (& & & +1 )= \
= mathfrak o .
end{array}
$$
Это равенство можно рассматривать как полиномиальное тождество относительно величины $ mathfrak A $.
Приравниваем нулю коэффициенты при $ mathfrak A^2, mathfrak A, 1 $ и получаем систему линейных уравнений, которой должны удовлетворять величины $ {b_j}_{j=0}^6 $:
$$
b_0 left(begin{array}{c} 1 \ 1 \ 0 end{array}right) + b_1 left(begin{array}{c} 0 \ 1 \ 1 end{array}right)+ b_2 left(begin{array}{c} 1 \ 1 \ 1 end{array}right)+ b_3 left(begin{array}{c} 1 \ 0 \ 1 end{array}right)+ b_4 left(begin{array}{c} 1 \ 0 \ 0 end{array}right)+b_5 left(begin{array}{c} 0 \ 1 \ 0 end{array}right)+
b_6 left(begin{array}{c} 0 \ 0 \ 1 end{array}right)= left(begin{array}{c} 0 \ 0 \ 0 end{array}right) .
$$
Все столбцы в левой части равенства различны, поскольку они соответствуют различным элементам поля $ mathbf{GF}(8) $. Именно в этом моменте существенно проявляется свойство примитивности элемента поля $ mathfrak A $: множество $ {mathfrak A^j}_{j=0}^6 $ совпадает со множеством
$$ {a_2 mathfrak A^2+a_1 mathfrak A+a_0 mid {a_0,a_1,a_2} subset {0,1}, (a_0,a_1,a_2) ne (0,0,0) }
$$
различных ненулевых полиномов над $ mathbf{GF}(2) $ степеней $ le 2 $.
Аналогичное утверждение справедливо и в общем случае поля $ mathbf{GF}(2^m) $.
Переписав эти соотношения в матричной форме, мы получим равенство вида
$$ mathbf H cdot left(begin{array}{l} b_0\ b_1\ vdots \ b_{n-1}end{array}right) = mathbb O $$
и столбцы матрицы $ mathbf H_{Mtimes (2^M-1)} $ — это все ненулевые $ M_{} $-разрядные двоичные столбцы. Но тогда матрица $ mathbf H $ — с точностью до перестановки — является проверочной матрицей кода Хэмминга.
.
Источники
[1]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.