ВУЗ:
Составители:
При построении циклических кодов удобно пользоваться табличными
разложения многочленов x
n
-1 на неприводимые многочлены, (которые делятся
на 1 и на самих себя)
∀ из этих многочленов может быть порождающим.
Пример. Рассмотрим (n,k) – коды, построенные на основе х
7
-1
x
7
-1=( x-1)(x
3
+x+1)(x
3
+x
2
+1)
Делители x
7
-1 Порождающий многочлен Код
x-1 g
1
(x) (7,6)
x
3
+x+1 g
2
(x) (7,4)
x
3
+x
2
+1 g
3
(x) (7,4)
( x-1)(x
3
+x+1) g
4
(x) (7,3)
( x-1)(x
3
+x
2
+1) g
5
(x) (7,3)
(x
3
+x+1)(x
3
+x
2
+1) g
6
(x) (7,1)
Код (7, 6) – в нем n-k=1
1 проверочный разряд (на четность)
(7, 1) – код с повторением
Оба они цикличны.
3.10 Задание циклических кодов
а) Циклический код может быть задан порождающим многочленом g(x)
Определение. h(x)=(x
n
-1)/g(x) – проверочный многочлен циклического
кода.
Многочлены g(x) и h(x) однозначно определяют друг друга => может
быть задан и проверяющий многочлен.
б) Так как циклический код – линейный код => его можно задать порож-
дающей и проверяющей матрицами.
3.10.1 Получение порождающей матрицы
Кодовая комбинация, соответствует порождающему многочлену g(x),
принадлежит циклическому коду (n, k), а по определению циклического кода
ему принадлежат и все циклические сдвиги этой комбинации.
Циклический сдвиг на один разряд вправо соответствует умножению
g(x)*X.
Так как степени многочленов g(x), X*g(x), X
2
*g(x), …, X
k-1
*g(x) различ-
ны => соответствующие им кодовой комбинации линейной независимы и могут
быть использованы в качестве строк порождающей матрицы:
g(x)X
...
)(*
)(
1-k
xgX
xg
G =
Если степень порождающего многочлена g(x) равна (n-k), то порождаю-
щая матрица имеет следующий вид:
24
При построении циклических кодов удобно пользоваться табличными
разложения многочленов xn-1 на неприводимые многочлены, (которые делятся
на 1 и на самих себя) ∀ из этих многочленов может быть порождающим.
Пример. Рассмотрим (n,k) – коды, построенные на основе х7-1
x7-1=( x-1)(x3+x+1)(x3+x2+1)
Делители x7-1 Порождающий многочлен Код
x-1 g1(x) (7,6)
x3+x+1 g2(x) (7,4)
x3+x2+1 g3(x) (7,4)
( x-1)(x3+x+1) g4(x) (7,3)
( x-1)(x3+x2+1) g5(x) (7,3)
(x3+x+1)(x3+x2+1) g6(x) (7,1)
Код (7, 6) – в нем n-k=1
1 проверочный разряд (на четность)
(7, 1) – код с повторением
Оба они цикличны.
3.10 Задание циклических кодов
а) Циклический код может быть задан порождающим многочленом g(x)
Определение. h(x)=(xn-1)/g(x) – проверочный многочлен циклического
кода.
Многочлены g(x) и h(x) однозначно определяют друг друга => может
быть задан и проверяющий многочлен.
б) Так как циклический код – линейный код => его можно задать порож-
дающей и проверяющей матрицами.
3.10.1 Получение порождающей матрицы
Кодовая комбинация, соответствует порождающему многочлену g(x),
принадлежит циклическому коду (n, k), а по определению циклического кода
ему принадлежат и все циклические сдвиги этой комбинации.
Циклический сдвиг на один разряд вправо соответствует умножению
g(x)*X.
Так как степени многочленов g(x), X*g(x), X2*g(x), …, Xk-1*g(x) различ-
ны => соответствующие им кодовой комбинации линейной независимы и могут
быть использованы в качестве строк порождающей матрицы:
g ( x)
X * g ( x)
G=
...
X k -1g(x)
Если степень порождающего многочлена g(x) равна (n-k), то порождаю-
щая матрица имеет следующий вид:
24
