Важнейшие групповые коды.

Из групповых кодов наиболее известны:

• Коды Хемминга

• Коды Голея

• Коды с единственной проверкой на чётность (нечётность)

Коды Хемминга.

Код Хемминга наиболее удобно определяется через число избыточных элементов. Пусть n-k = r, тогда n = 2^r – 1, k = 2^r – r – 1, d_min = 3. В качестве проверочной матрицы H Хемминг предложил использовать матрицу размером n столбцов и n – k = r строк, у которой в качестве столбцов записаны все ненулевые r разрядные двоичные числа в упорядоченной записи.

“1”“2””3””4””5””6””7”

Сумма “1”, “2”, “3” = 0 d_min = 3

Этот код может исправлять однократные ошибки.

Таблица декодирования состоит из 2^n-k строк и 2^k столбцов. Синдром совпадает с номером ошибки.

Код Голея.

(23,12) d_min = 7 – двоичный код

(11,6) d_min = 5 – троичный код

Коды строго лежат на границе Хемминга:

- для двоичного кода

- для троичного кода

Коды с единственной проверкой на чётность: (n , n-1).

Это коды с максимально разнесённым расстоянием:

d-1 = n-k

d = n-k+1

Коды с единственной проверкой на чётность задаются с помощью проверочной матрицы:

H(n ,n-1) = [111...1], где

а) число строк равно числу проверочных элементов (=1);

б) единицы на местах тех элементов, которые охвачены проверкой (n единиц);

в) d=2, так как при сложении двух любых столбцов получаем 0.

При d=2 можно только обнаруживать однократные ошибки. Никакие ошибки чётной кратности этот код обнаруживать не будет, только ошибки нечётной кратности. Следовательно, код обнаруживает половину ошибок.

Циклические коды.

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

Циклические коды -это разновидность групповых кодов. Обозначение:(n,k).

Два определения циклического кода:

1) Циклическим (n,k)-кодом называют такой групповой код, для которого справедливо: если последовательность (a0, a1, ... , an-1) принадлежит коду, то и n-последовательность вида (an-1, a0, a1, ... , an-2), полученная путём циклического сдвига элементов, указанных в комбинации, на единицу вправо, также принадлежит этому коду (циклический сдвиг делается с помощью умножения на x).

Обычно комбинации циклических кодов представляют в виде многочленов f(x), степень которых не превышает (n-1):

(a0, a1, ... , an-1) соответствует a₀x⁰+a₁x¹+a₂x²+…+a_n-1x^n-1

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

2) Здесь используется возможность умножения и деления. Циклическим (n , k)-кодом называют множество многочленов степени (n-1) и менее, каждый из которых делится без остатка на некоторый многочлен g(x), степень которого равна (n-k). Этот многочлен g(x) должен быть сомножителем (делителем) двучлена (xⁿ+1). Многочлен называют порождающим многочленом.

Если получаем xⁿ+1=0, то два эти определения сходятся (xⁿ=1).

Кодовые комбинации циклического кода представляются в виде многочленов. Сложение многочленов не изменяет их степени и эквивалентно сложению векторов, поэтому множество векторов (n-1) и менее по операции сложения многочленов представляет собой группу, т.е. групповой код. Однако умножение и деление векторов изменяет их степень. Для того чтобы обеспечить замкнутость по операции умножения векторов производят умножение многочленов по модулю многочлена(x^(n-1)).

В этом случае многочлен (xⁿ+1) является нулём, также как двойка является нулём при действиях по mod2.

Понятие о кольце и поле.

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

1. Замкнутость.

a,bR, то ab=cR, где R- кольцо.

2. Операция умножения ассоциативна.

a(bc)=(ab)c

3. Элементы кольца удовлетворяют дистрибутивному закону.

a(b+c)= ab+ac

Роль подгруппы в группе в кольце выполняет идеал. Если элемент кольца умножить на элемент идеала, то получим идеал.

Рассмотрим множество всех целых чисел, а идеал возьмём следующим образом: выпишем все чётные числа.

... -4 -2 {0} 2 4 6 8 ... -идеал (1)

(mod 2)

... -3 -1 {1} 3 5 7 9 ... (2)

{}-минимальные положительные элементы

{1}-минимальное число, не вошедшее в идеал

Вводя действие над числами (mod2), получили два класса вычетов, следовательно, получили кольцо.

Идеал как подгруппа по операции сложения. Если умножить (2) на (1), то результаты будут во множестве (1).

... -3 {0} 3 6 9 12 ... (3)

... -2 {1} 4 7 10 13 ... (mod 3)

... -1 {2} 5 8 11 14 ...

Если 3*4 =12, а 12 по mod 3 является нулём, а ноль входит в (3).

Множество классов вычетов кольца, также образуют кольцо.

Поле - множество элементов произвольной природы, для которых задано два действия: сложение и умножение и по этим действиям удовлетворяются все групповые аксиомы.

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

Классы вычетов {0} и {1} по mod 2.

Наличие единичного элемента:

0 1

Наличие обратных элементов:

Обратные элементы существуют только не для нулевых элементов.

По аналогии с кольцом классов вычетов целых чисел, можно построить кольцо классов вычетов многочлена по модулю многочлена (xⁿ +1). Этих классов вычетов будет ровно 2ⁿ , если коэффициенты многочлена взяты из двоичного кода. Для этого кольца классов вычетов можно построить идеал, если взять все многочлены (классы вычетов), кратные некоторому многочлену g(x)(многочлен g(x) образует свой класс вычетов).

В теории кодирования доказывается, что если некоторый многочлен g(x) образует идеал, то он должен быть сомножителем (xⁿ+1), а многочлен

h(x)= образует нулевое пространство для этого идеала.

Код Рида - Соломона.

n = q-1, где q-основание кода.

Если q =2, то получаем код, состоящий из одного элемента (n = 2-1).

Расширенные коды: p=q^m, где p-число элементов поля. Тогда при q =2: n=2^m-1 (т.е. берём не числовое поле, а поле из последовательностей нулей и единиц).

Запишем множество многочленов по mod (xⁿ+1):

{0}, xⁿ +1, x (xⁿ +1), …

{1}, xⁿ +1+1, xⁿ⁺¹ +x+1, …

{x}, …

{x+1}, …

{x²}, …

{x² +1}, …

{x² +x+1}, …

:

{x^n-1 +x^n-2 +x+1}, …

Всего получили 2ⁿ различных кодовых комбинаций. Надо из 2ⁿ кодовых комбинаций выбрать 2^k< 2ⁿ .Для этого: если это множество построено по модулю многочлена f(x) и при этом этот многочлен состоит из:

f(x)=g(x)*h(x)=0, то идеал будет включать все многочлены, кратные g(x), а его размер будет k.

Можно построить идеал на основе h(x). Идеал будет кратен h(x), а его пространство будет (n-k).

Мы получили циклический код, у которого каждый многочлен кратен многочлену g(x) или h(x).

Рассмотрим поле. Хотим перейти к полю с большим основанием. Это можно сделать либо расширением (p=2^m), либо увеличением основания q.

Простые и расширенные поля.

Простыми полями называют поля, сформированные по модулю простого числа (простое число делится на 1 и на себя).

Простое поле представляет собой кольцо классов вычетов по модулю простого числа с конечным числом элементов. Для конечных полей используется обозначение GF(q), где q- число элементов поля, q = p (простое число).

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

Пример:

Есть GF(q), q=5

Элементами этого поля являются {0}

{1}

{2}

{3}

{4}

2⁰=1

2¹=2

2²=4

2³=8 (8 по mod 5 будет 3)

Следовательно, 2 –это примитивный элемент поля.

Расширенным полем называют такое поле, элементами которого являются последовательности заданной длины, состоящие из элементов основного поля.

q = p=2 GF(2) (элементы поля: 0 и 1)

Как построить элементы расширенного поля?

GF(q^m) GF(2^m) (для расширенного поля)

Возьмём m=2:

GF(2)=0,1 -простое поле

GF(2²)=00, 10, 01, 11 -расширенное поле (все последовательности нулей и единиц).

Обозначим многочлены:

f(x) = 00=0

f(x) =10=1

f(x) =01=x

f(x) =11=x+1

Элементы расширенного поля можно получить как кольцо классов вычетов по модулю неприводимого многочлена степени m, коэффициенты которого взяты из основного поля.

Для того чтобы построить поле GF(2^m), надо построить кольцо классов вычетов неприводимого многочлена (x^m + … +1) с коэффициентами основного поля.

m=2 x² +x+1

П(a)=α² +α+1 (вместо x подставляем α).

Строим элементы поля:

0 = 0 = 00

α⁰ = 1 = 10

α¹ = α = 01

α² = 1+α = 11 (т.к. α² по модулю (α² +α+1) равно 1+α)

Если α⁰ разделить на(α² +α+1),то остатком будет α⁰

(т.к. деление начнётся с α²)

Порождающие и проверочные матрицы для циклических кодов.

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

Порождающая матрица циклического кода строится как множество из k многочленов, кратных многочлену g(x):

Пример1: по второму определению циклического кода

n=7 x⁷ +1=(x+1)(x³ +x+1)(x³ +x² +1)

В качестве g(x) можно взять:

g₁(x)=x+1

g₂(x)=x³ +x+1

g₃(x)=x³ +x² +1

g₄(x)=(x+1)(x³ +x+1)

g₅(x)=(x+1)(x³ +x² +1)

g₆(x)=(x³ +x+1)(x³ +x² +1)

Это будут следующие коды: (7,6) d=2

(7,4) d=3

(7,4) d=3

(7,3) d=4

(7,3) d=4

(7,1) d=7

Для кода Хемминга: G_(7,4)= =приведём к канонической

форме и получим:G_(7,4)=

Проверочная матрица: H=[I₃ R^T] =,где I₃ –единичная матрица 3 3

Последовательности (α₀, α1, ... ,α _n-1)соответствует многочлен α₀x⁰ + … +α₀x ^n-1

Как можно построить проверочную матрицу?

xⁿ +1=g(x) h(x)=0

Для g(x) есть ортогональный многочлен, следовательно можно строить проверочную матрицу на основе g(x).

g(x)- порождающий многочлен

h(x)- проверочный многочлен степени k

Надо найти h(x).

Способ 1 (см. пример1):

(x⁷+1) / (x³+x+1) = (x⁴+x²+x+1) = h(x) (деление столбиком)

Способ 2:

h(x)=(x+1)(x ³+x ²+1)=x⁴+x³+x+x³+x²+1=x⁴+x²+x+1

Строим H_(n,r) =

Для нашего примера H_(7,4)==приведём к канонической

форме и получим H_(7,4)=

Пример2: надо умножить (a₀+a₁x+a₂x²)(b₀+b₁x+b₂x² ) по mod x³.

a₀b₀ + a₀b₁x + a₀b₂x² +

+ a₁b₀x + a₁b₁x² + a₁b₂x³ +

+ a₂b₀x² + a₂b₁x³ + a₂b₂x⁴

Приведём по mod x³:

a₀b₀ + a₀b₁x + a₀b₂x² +

a₁b₂ + a₁b₀x + a₁b₁x² +

a₂b₁ + a₂b₂x + a₂b₀x²

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

H = g(x)h(x)=0 mod(x ⁿ+1)

x⁷+1=(x+1)(x ³+x+1)(x ³+x²+1)

С помощью неприводимого многочлена П(α)=α³+α+1 можно построить поле GF(2³):

α⁰ = 1 = 100

α¹ = α = 010

α² = α² = 001

α³ = 1+α = 110

α⁴ = α+α² = 011

α⁵ = 1+α+α² = 111

α⁶ = 1+α² = 101

Построили элементы поля GF(2³ ) по модулю неприводимого многочлена.

В теории Галуа доказано, что имеется однозначная связь между корнями двучлена (xⁿ+1) и ненулевыми элементами поля GF(qⁿ), а именно: корни двучлена (xⁿ+1) являются ненулевыми элементами поля GF(qⁿ).

Возьмём двоичное поле GF(2^m). Установим связь между:

2^m-1

X + 1 и GF(2^m), где (2^m-1) – всего ненулевых элементов поля GF(2^m),

α⁰= … = 100

: :

α⁶= … = 100

Распределим все элементы поля по многочлену:

x⁷+1=(x+1)(x ³+x+1)(x ³+x²+1)

α⁰ α¹ α² α⁴ α³ α⁶ α⁵ (т.к. α¹² = α⁷+α⁵ = 1+α⁵ = α⁵)

Корректирующие свойства циклических кодов.

Корректирующие свойства циклических кодов задаются следующими двумя теоремами, авторами которых являются Боуз и Чоудхури. Впоследствии оказалось, что аналогичные результаты получил француз Хоквинчел. Поэтому коды, удовлетворяющие теоремам называются кодами ВЧХ.

Теорема1. Для любых чисел l и t можно построить циклический код с длиной кодовой комбинации n=2^l-1. Число избыточных элементов n-k = l*t. Минимальное кодовое расстояние d 2t +1.

Эта теорема говорит о потенциальной возможности построения кода с указанными параметрами.

Теорема2 (эта теорема говорит как реализовать теорему1). Если среди корней порождающего многочлена есть числа вида

α^m0 , α^{m0 +1} , α^{m0 +2} , … , α^{m0 +d-2} , то минимальное кодовое расстояние циклического кода с данным g(x) :

dmin d , где d -конструктивное расстояние.

Пример1: пусть l =3, t =1.

при l =3 : n =7

при t =1: n-k =3. Следовательно получили код (7,4)

g1(x) = x ³+x+1 , корни многочлена: α¹, α², α⁴ (два подряд идущих корня α¹ и α² )

m0 =1

m0+d-2=2;

d =3

g2(x) = x ³+x ²+1 , корни многочлена: : α³, α⁵, α⁶ (два подряд идущих корня α⁵ и α⁶ )

m0 =5

m0+d-2=6;

d =3

Для кода (7,6): g(x) =1+x (один корень), dmin =2;

Для кода (7,3): g(x) = (1+x) (1+x+x³) , корни: α⁰, α¹, α², α⁴ (три подряд идущих корня α⁰, α¹, α²), dmin =4;

Укорочение кодов.

Из любого группового (n,k)-кода можно получить (n-i,k-i)-код. Для этого необходимо в порождающей матрице (n,k)-кода, записанной в канонической форме G(n,k)=[Rk , (n-k)Ik] ,вычеркнуть i крайних справа столбцов и i нижних строк. Оставшаяся часть порождающей матрицы даст порождающую матрицу кода (n-i,k-i) в канонической форме.

Рассмотрим код (5,3):

G(5,3)= , следовательно G(4,2)=

Укорочение проверочной матрицы происходит по следующему правилу: необходимо в проверочной матрице (n,k)-кода, H(n,k)=[In-kR^T ], вычеркнуть i крайних справа столбцов (проверочные элементы не вычёркиваются, только информационные). Оставшаяся часть проверочной матрицы даст проверочную матрицу кода (n-i,k-i).

H(5,3)= , следовательно H(4,2)=

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

Процедуры кодирования и декодирования для циклических кодов.