Зразки розв'язування задач до розділу 10

 

Приклад 1  Лінійний блоковий (4, 7)-код заданий твірною матрицею вигляду

.

                Побудувати перевірну матрицю і систему перевірних рівнянь коду. Закодувати комбінації 1010, 1110. Визначити синдром виправлення поодиноких помилок у комбінаціях коду. Використовуючи синдром, визначити й виправити помилку в комбінаціях 1010101, 1000100.

Розв'язання

                Перевірна матриця заданого коду має розмірність (n-k, n) і таку структуру:

,

                                                                    

де - транспонована перевірна (права) частина твірної матриці G;  - одинична підматриця.

                Кількість інформаційних елементів коду k=4, перевірних r=3, довжина кодових слів n= k+r=7.

                Кодові слова даного лінійного блокового коду будуються так:

u=(u1, u2, , un) = (m1, m2, m3, m4, r1, r2, r3),

де m1, m2, m3, m4 - інформаційні символи; r1, r2, r3 – перевірні символи, що додають кодером до блоку повідомлення m=(m1, m2, m3, m4).

                Знайдемо систему перевірних рівнянь, що визначають правила знаходження перевірних символів (контрольних сум) коду.

1-й спосіб.

                З рівняння кодового синдрому

                                              

визначаємо правила знаходження перевірних символів коду:

                                                                                                                  ()

2-й спосіб.

                Кодове слово лінійного блокового коду утворюється множенням інформаційного повідомлення на твірну матрицю:

                Звідси випливає система перевірних рівнянь коду ().

                Закодуємо задані інформаційні послідовності,  помноживши їх на твірну матрицю коду G або обчисливши контрольні суми з () і дописавши їх у правій частині кодового слова:

(1010) =(1010011); (1010)(1010011).

(1110) =(1110000); (1110)(1110000).

                На приймальному боці обчислюється вектор синдрому

               

де y – прийнята кодована послідовність; H – перевірна матриця.

                Кодовий синдром служить ознакою наявності помилок у прийнятій послідовності: якщо вектор синдрому дорівнює нулю, то прийнята послідовність є кодовим словом даного коду, інакше в ній є помилки.

                Використання синдрому дозволяє не тільки виявляти, але й виправляти однократні помилки в коді: у випадку наявності в прийнятій послідовності однієї помилки вектор синдрому збігається з тим із стовпців перевірної матриці, номер якого відповідає номеру помилкового біта.

                Перевіримо на наявність помилок комбінації 1010101, 1000100, і у випадку виявлення помилки виправимо її.

Для цього обчислюємо синдром прийнятого вектора:

(1010101)H=(1010101)=(110)0, отже, у даній послідовності є помилка. Кодовий синдром S=(110) збігається із 1-м стовпцем перевірної матриці, що свідчить про наявність помилки у 1-му біті.

Виправляємо помилку: (1010101) (0010101).

Декодуємо послідовність, вилучивши контрольні суми:

(0010101) (0010).

(1000100)H=(1000100)=(010)0 – кодовий синдром S=(010) збігається з 6-м стовпцем перевірної матриці, що свідчить про помилку у 6-му біті.

Виправляємо помилку: (1000100)(1000110).

Декодуємо послідовність, прибравши контрольні суми: (1000110) (1000).

Приклад 2  Побудувати твірну матрицю лінійного блокового коду, здатного виправляти поодинокі помилки при передачі 8 повідомлень. Побудувати перевірну матрицю коду. Навести приклад кодування і декодування повідомлень із виявленням і виправленням помилки.

Розв'язання

                Кількість бітів, необхідна для кодування 8 повідомлень різними комбінаціями двійкового коду, визначається з нерівності

N  2k,

де N – об'єм алфавіту джерела повідомлень; k – довжина кодової комбінації у бітах.

                Звідки випливає, що k  log2 N.

                У даному випадку для кодування N=8 повідомлень необхідна кількість бітів k  3.

                Довжина кодових слів при кодуванні лінійним блоковим кодом інформаційних повідомлень довжиною k символів  n= k+r, де r – кількість перевірних символів, що додаються до інформаційного повідомлення для забезпечення можливості виявлення і/або виправлення помилок, що виникають при передачі по каналу зв'язку із завадами.

                Знайдемо кількість перевірних розрядів r, необхідну для виправлення помилок кратності l=1.

                Для того щоб лінійний блоковий код міг виправляти помилки кратності не більшої l, необхідно і достатньо, щоб найменша кодова відстань між його словами dmin відповідала нерівності

dmin ≥ 2l+1.

                У даному випадку для виправлення помилок ваги l=1 мінімальна кодова відстань dmin  3.

                Мінімальну кількість перевірних розрядів r визначаємо, скориставшись формулою нижньої границі Плоткина:

r   2dmin - 2 – log2 dmin.

                У даному випадку необхідна кількість перевірних елементів  r =  23 – 2 – log2 3    4 – 1,585 =3.

                Тоді довжина кодового слова n= k+r = 3+3=6.

                Твірна матриця лінійного блокового коду складається із двох частин: інформаційної Ik×k (одиничної підматриці) і перевірної Рkr. Перевірна підматриця Pk(n-k) будується підбором r-розрядних комбінацій з кількістю одиниць у рядку ≥ dmin-1 і кодовою  відстанню між рядками ≥dmin-2. При цьомусі рядки твірної матриці лінійно незалежні, вага кожного кодового слова, що входить у твірну матрицю, і кодова відстань між ними ≥dmin.

                Наведемо можливий варіант твірної матриці лінійного блокового (3,6)-коду:

.

                   Ik×k    Pk(n-k)

                Перевірна матриця заданого коду складається із транспонованої перевірної частини твірної матриці P(n-k)×k  і одиничної підматриці I(n-k)×(n-k):

.

                                P(n-k)-k   Ik×k

                Виходячи з твірної матриці, будуємо таблицю всіх можливих кодових слів заданого коду:

                (m1, m2, m3) (u1, u2, u3, u4, u5, u6)= =(m1, m2, m3, r1, r2, r3),

де кодове слово u= mG(k, n).

                1) (000)(000000);  2) (001)(001110);

                3) (010)(010011);  4) (011)(011101);

5) (100)(100101);  6) (101)(101011);

7) (110)(110000);  8) (111)(111001).

                Неважко переконатися, що мінімальна кодова відстань отриманого коду dmin=3.

                Іншим способом таблицю кодів можна побудувати, розглянувши всі можливі лінійні комбінації (порозрядні суми за модулем 2) кодових слів, що входять у твірну матрицю коду.

                Припустимо передається повідомлення m=(101).

                Кодовим словом на виході кодера буде послідовність

                               u= mG = (101) = (101011).                            Нехай при передачі цього кодового слова по каналу зв'язку із завадами в ньому виникла помилка. Наприклад, прийнята послідовність y=(101111).

                Для декодування прийнятої послідовності на прийомній стороні обчислюється кодовий синдром

S= yH,

де y – прийнята кодована послідовність; H - транспонована перевірна матриця.

                Обчислимо синдром прийнятого вектора y:

                               S= (101111)= (100)  0 - значення синдрому збігається із 4-м стовпцем перевірної матриці H, отже, помилка виникла в 4-му розряді.

Виправляємо помилку і декодуємо кодове слово так:

                (101111)(101011)(101).