Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Розв'язання. Кількість інформаційних елементів заданого інформаційного повідомлення m= (0111) k=4
|
|
Кількість інформаційних елементів заданого інформаційного повідомлення m= (0111) k =4. Кількість перевірних елементів коду визначається степенем твірного полінома g(x) – у даному випадку кількість перевірних елементів r =3. Тоді довжина кодового слова n = k + r =4+3=7.
Подамо задану інформаційну послідовність m =(0111) у вигляді многочлена m (x)= 0 × x 0 + 1 × x 1 + 1 × x 2 + 1 × x 3 = x + x 2 + x 3.
Закодуємо задане повідомлення за таким алгоритмом:
1) многочлен інформаційного повідомлення m (x) множимо на xn-k:
xn-k × m (x)= x3 (x + x2 + x3)= x4 + x5 + x6;
2) знаходимо остачу r (x) від ділення добутку xn-k × m (x) на твірний поліном коду g(x):
x 6 + x 5 + x 4 x 3 + x + 1
+ x6 + x4 + x3 x 3 + x 2
x 5 + x 3
+ x5 + x3 + x2
r (x)= x2 = 0× x0 +0× x1 +1× x2 ® (001);
3) кодовий поліном заданого інформаційного повідомлення знаходимо так:
u (x)= r (x)+ xn-k × m (x) = x2 + x4 + x5 + x6 =0× x0 +0× x1 +1× x2+ 0× x3 +1× x4+
+ 1× x5 +1× x6,
йому відповідає кодове слово u =(0010111).
Даний лінійний завадостійкий код, твірний поліном якого g(x) має степінь r=n-k= 3, здатний виправляти помилки кратності l =1.
Виправимо помилку в комбінаціях коду 0110111, 1101010.
1) Прийнятій комбінації y= (0110111) відповідає многочлен y (x)= x + x2 + x4 + x5+ x6.
Перевіримо дану комбінацію на наявність помилки: для цього розділимо її многочлен на твірний поліном коду:
x 6 + x 5 + x 4 + x 2 + x x 3 + x + 1
+ x6 + x4 + x3 x 3 + x2 + 1
x5 + x3 + x2 + x
+ x5 + x3 + x2
s (x)= x – поліном остачі не дорівнює нулю, відтак, у заданій комбінації є помилка.
Поліном остачі s (x)= x= 0 ×x0+ 1 ×x1+ 0 ×x2 має степінь n-k-1 – у даному випадку 2 (оскільки степінь многочлена дільника n-k =3), і йому відповідає вектор (010)¹ 0.
Вага Хеммінга вектора остачі визначається кількістю одиниць в ньому: w (010)= 1 £ l, де l =1 – кратність помилок, що виправляються кодом.
Вага остачі w ≤ l, тому виправлену комбінацію одержуємо додаванням многочленів прийнятої послідовності і остачі від її ділення на твірний поліном коду:
y (x) + s (x)= x6 + x5 + x4 + x2 + x + x = x6 + x5 + x4 + x2 =
= 0× x0 + 0× x1 + 1× x2 + 0× x3 + 1× x4 +1× x5 + 1× x6 ® (0010111).
Одержана у такий спосіб комбінація декодируется так:
(0110111) ® (0010111)® (0111).
2) Прийнятій комбінації y= (1101010) відповідає многочлен y (x)= 1 + x + x 3 + x 5.
Перевіримо дану комбінацію на наявність помилки. Для цього розділимо її на твірний поліном коду:
x 5 + x 3 + x + 1 x 3 + x + 1
+ x5 + x3 + x2 x 2
s (x)= x2 + x + 1 ¹ 0.
Многочлен остачі s (x)= 1+x+x2 визначає вектор s= (111), вага якогого w (111)= 3 > l, де l – кратність помилок, що виправляються кодом.
Вага остачі більше кратності помилок l =1, тому необхідно виконати циклічний зсув кодованої послідовності (1101010) на 1 розряд вправо: (1101010) ® (0110101).
Одержаній комбінації відповідає многочлен
y (x)=0× x0 +1× x1+ 1× x2 +0× x3 +1× x4 + 0× x5+ 1× x6 = x+x2 + x4+x6.
Знайдемо остачу від ділення даного многочлена на твірний поліном коду:
x 6+ x 4+ x 2 + x x 3 + x + 1
+ x6 + x4 + x3 x3 + 1
x3+ x 2 + x
+ x3 + x + 1
s(x)= x 2 + 1 ®(101).
Вага остачі w (101)= 2 > l.
Вага остачі більше l = 1, тому знову виконуємо циклічний зсув кодованої послідовності на 1 розряд вправо: (0110101) ® ®(1011010). Одержаній комбінації відповідає многочлен
y (x)=1× x0 +0× x1+ 1× x2 +1× x3 +0× x4 +1× x5 + 0× x6 = 1+x2 + x3+x5.
Розділимо даний многочлен на твірний поліном коду:
x 5+ x 3+ x 2 + 1 x 3 + x + 1
+ x5 + x3 + x2 x2 + 1
s(x)= 1 ®(100).
Вага вектора остачі w (100)= 1 £ l – кратності помилок, що виправляються кодом. Таким чином одержуємо кодовий поліном u¢ (x) додаванням останнього многочлена і многочлена його остачі від ділення на твірний поліном коду:
u¢ (x)= x5+ x3+ x2 + 1+ 1 = x2 + x3+ x5 = 0× x0 + 0× x1+ 1× x2 + 1× x3 +
+0× x4 + 1× x5+ 0× x6 ® (0011010).
Для того щоб одержати закодовану послідовність, виконуємо циклічний зсув кодового слова u ¢ (x) назад (вліво) на 2 розряди:
(0011010) ® (1101000).
Таким чином, одержуємо виправлену кодову комбінацію u= (1101000), в якій контрольним сумам відповідають молодші розряди в лівій частині кодового слова.
Отже, повідомлення декодуємо так:
(1101010) ® (1101000) ® (1000).
Відповідь: (0111)® (0010111); (0110111) ® ® (0010111)®(0111), (1101010) ® (1101000) ® (1110).
Приклад 3 Циклічний (4, 7)- код заданий твірним поліномом g(x)=1+x+x 3. Визначити синдром виправлення поодиноких помилок цим кодом. Побудувати перевірну й твірну матриці коду. Декодувати повідомлення (1001110).
Date: 2015-11-15; view: 435; Нарушение авторских прав