Линейно групповые коды. Декодирование линейно групповых кодов

Страницы работы

3 страницы (Word-файл)

Содержание работы

Линейно групповые коды (ЛГК)

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

Свойства ЛГК:

1) Сумма (разность) кодовых векторов даёт вектор принадлежащий данному коду.

ЛГК относят к систематическим кодам. Минимальное кодовое расстояние равно минимальному весу ненулевых кодовых векторов. ЛГК обозначается (П, nu) и задаются с помощью производящих матриц. Производящая матрица строится, как результат слияния информационной (И) и проверочной (П) матриц.

Матрица имеет nk – столбцов и nu – строк.

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

Вес каждой строки матрицы П WП = d0 – 1. Т.о. пораждающая матрица С приводится к следующему виду:

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

1)  Их можно получить как результат сложения строк производящей матицы составленных в различных сочетаниях.

2)  ЛГК можно построить по производящей матрице, используя информационную часть кода, путём суммирования строк матрицы П.

Пример: Построить производящую матрицу для ЛГК, способную исправлять одиночную ошибку при передачи кода на 16 сообщений.

nu = 4;              nk = log(nu + 1 + log(nu + 1)) = 3

d0 = 3;               n = 7 – значность кода

                      (единичная матрица)

Пример: Построить образующую матрицу ЛГК, способную передавать 100 сообщений и исправлять одиночную ошибку.

N = 100 = ;              nu = 7;              nk = 4;              n = 11;

Строим производящую матрицу:


 

Пример: Построить групповой код по заданной производящей матрице

Выписываем информационные части кода:

1)   0000           5) 0010

2)   1000           6) 1010

3)  0100           7) 0110             и т.д.

4)  1100           8) 1110

К каждой информационной части строим конкретный разряд:

1)  000

2)  111 – берём первую строку матрицы П

3)  110 – 2 – ю

4)  111 – складываем первую и вторую строку

       110

       001

5)  101

6)  111

       101

       010    - 1 - я + 3 - я

7)  110

101

       011    - 2 - я + 3 - я

8)  111

110

       001

       100

Декодирование ЛГК

В процессе декодирования осуществляется проверки по определённой схеме. Число проверок равно числу контрольных разрядов. S(S1, S2, …,) – строится проверочный вектор, который называется синдром. Если вес синдрома равен нулю, то комбинация принята правильно. Если какой – либо разряд содержит единицу, то имеется ошибка. Каждому разряду соответствует свой синдром. Вид синдрома определяется с помощью производящей матрицы. Набор синдромов содержится в специальной проверочной матрице H, которая строится из матрицы H = [ПТ×Ink] Ink  - единичная матрица. Столбцы матрицы представляют значение синдрома для каждого разряда.

Схема проверок: принятый сигнал vx представляем в виде информационной части

vx = (a1, a2, …,an, P1, P2,…,Pm)

Схема проверок строится:

1)  Проверка S1

Суммируется разряд P1 и те разряды из информационной части a1 + …+ an, номера которых совпадают с номерами ненулевых разрядов первого столбца матрицы П.

2) Проверка S2

Суммируется разряд P2 и те разряды информационной части a1 + …+ an, номера которых совпадают с номерами ненулевых разрядов второго столбца матрицы П.

Пример: Задана производящая матрица C7,4 и составим схему проверок

                   И                      П

S1 = P1 + a2 + a3 + a4

S2 = P2 + a1 + a3 + a4

S3 = P3 + a1 + a2 + a3

Строим H:

Если разряды синдрома соответствуют одному столбцу матрицы Н, т.е. S1 = 0, S2 = 1, S3 = 1, то ошибка в первом разряде.

Пример: Пусть имеется информационная часть ЛГК, которая исправляет одиночную ошибку. Дана производящая матрица С7,4. Получим корректирующие разряды, для этого сложим первую и вторую строку, следовательно, полный код.

a1a2 a3a4P1P2P3

v1 = 1100110                vx = 1101110

Cхема проверок осталось такой же

Проведём проверки:

 
S1 = 1 + 1 + 0 + 0 = 0

S2 = 1 + 1 + 0 + 0 = 0               

S3 = 0 + 1 + 1 + 0 = 0

 
Пусть vx = 1101110, т.е. ошибка в четвёртом разряде.

S1 = 1 + 1 + 0 + 1 = 1

S2 = 1 + 1 + 0 + 1 = 1                            - это соответствует ошибке в четвёртому разряду

S3 = 0 + 1 + 1 + 1 = 1

Похожие материалы

Информация о работе