Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Теорія інформації та кодування. Тема 6. Недвійкові завадостійкі коди. Носов В.В.
Лекція 13(3.3). Недвійкові коди
Навчальні питання
1. Недвійкові первинні коди 1
2. Недвійкові коди, що виявляють помилки 2
3. Недвійкові коди, що виправляють помилки 4
Час – 4 год.
Література.
Вступ
Недвійкові коди за аналогією з двійковими можна поділити на такі:
Недвійкові первинні коди використовуються у телекомунікаційних системах та мережах і системах телемеханіки. Далі наведені вирази для розрахунку кількості кодових комбінацій, які можна отримати при побудові таких первинних кодів (вони пов’язані з відповідним розділом математики, який називається комбінаторикою).
Код на перестановки:
тут і далі q – потужність алфавіту коду, n – довжина кодової комбінації.
Перестановкой из элементов (например, чисел ) называется всякий упорядоченный набор из этих элементов.
Код на певне число розміщень:
N0= = q!/(q–n)!, q > n.
Размещением из элементов по называется упорядоченный набор из различных элементов некоторого -элементного множества.
Код на певне число сполучень:
N0= = q!/[(q–n)!n!], q > n.
Сочетанием из по называется набор элементов, выбранных из данных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Код на всі сполучення:
N0 = qn, qn.
Змінно-якісний код:
N0 = q(q–1)n–1 .
Задача 10.2.1
Побудувати трійкові первинні коди (): на перестановки при , на певне число розміщень при , на певне число сполучень при , на всі сполучення при та змінно-якісний при .
Розв’язання. Визначимо кількість комбінацій при заданих параметрах та подамо їх для всіх цих кодів:
Недвійкові коди, що виявляють помилки, можуть бути побудовані або
В обох випадках досягається збільшення кодової відстані до значення, що дозволяє виявити ту чи іншу кількість помилок у кодовій комбінації.
Код з перевіркою за будується за аналогією з двійковим кодом з перевіркою на парність, але з тією різницею, що виконується доповнення кодової комбінації первинного q-ічного коду перевірочним елементом таким чином, щоб сума усіх елементів дорівнювала нулю за . Значення перевірочного елемента у даному разі визначається різницею між q та сумою значень всіх елементів первинної кодової комбінації за .
Такий код має незначну надмірність і дозволяє виявити наявність помилок у кодовій комбінації, якщо сума усіх елементів (інформаційних та перевірочного) за відрізняється від нуля.
Код з простим повторенням є аналогом двійкового коду з простим повторенням, в основу якого покладено просте повторення первинної кодової комбінації. Алгоритм побудови коду має вигляд:
,
де – інформаційний елемент, що знаходиться на i-ій позиції інформаційної частини кодової комбінації; – перевірочний елемент, що знаходиться на i-ій позиції перевірочної частини кодової комбінації; – кількість інформаційних елементів.
Надмірність коду . Код дозволяє виявити всі помилки, за винятком деяких помилок на однакових позиціях в інформаційній та перевірочній частинах коду.
Задача10.2.2
Закодувати комбінацію трійкового коду на всі сполучення трійковими кодами, що виявляють помилки: з перевіркою за (при ) та з повторенням. Показати процес виявлення однократної помилки, визначити та порівняти надмірності цих кодів.
Розв’язання. Кодова комбінація трійкового коду з перевіркою за буде мати вигляд , а трійкового коду з повторенням – .
Припустимо, що у комбінації трійкового коду з перевіркою за виникла однократна помилка, вектор якої . Тоді сума за . У декодері перевіряється за сума елементів одержаної кодової комбінації. У цьому разі вона буде дорівнювати 2, тобто відрізнятися від 0, що вказує на наявність помилки у комбінації. Надмірність коду .
Припустимо, що у комбінації трійкового коду з повторенням виникла однократна помилка, вектор якої . Тоді сума за . Порівнюючи першу (1...3 розряди) і другу (4...6 розряди) частини кодової комбінації побачимо, що вони відрізняються у другому і п’ятому розрядах. Це вказує на наявність помилки у прийнятій кодовій комбінації. Надмірність коду .
Таким чином .
Недвійкові коди, що виправляють помилки, поділяють на
Блокові q-коди, як і аналогічні двійкові, призначені для виправлення, головним чином, незалежних помилок. Однак, на відміну від двійкових, один елемент недвійкового коду несе біт інформації у залежності від методу побудови конкретного коду. Така особливість недвійкових кодів дає підставу стверджувати, що блоковий недвійковий код дозволяє виправляти умовний пакет помилок з біт інформації, який, якби він виникнув у аналогічному двійковому коді, не міг бути виправлений ним. Це є однією з переваг використання недвійкових кодів, що виправляють помилки.
Код з багатократним повторенням застосовується при передачі інформації по каналам з високим рівнем завад. Цей код містить інформаційних елементів, а кількість перевірочних елементів залежить від числа повторень, причому кожний перевірочний елемент збігається з відповідним йому інформаційним. Таким чином довжина кодової комбінації: . Алгоритм побудови коду:
де – інформаційний елемент, що знаходиться на i-ій позиції інформаційної частини кодової комбінації; перевірочний елемент, що знаходиться на i-ій позиції j-го повторення.
Процедура виявлення помилок у прийнятій кодовій комбінації полягає у порівнянні однойменних інформаційних і перевірочних розрядів. Їх незбіг говорить про наявність помилок у прийнятій комбінації. При виправленні помилок у комбінації застосовується мажоритарний принцип виправлення для кожного інформаційного елемента, тобто "голосування за більшістю", коли за істинне значення приймається те, яке частіше зустрічається у цьому інформаційному і відповідних йому перевірочних елементах.
При -кратному повторенні надмірність коду .
Код з простим повторенням та перевіркою за є комбінованим використанням двох недвійкових кодів, що виявляють помилки: з простим повторенням та перевіркою за . Це дає можливість одержати код, що виправляє однократні помилки. В основу коду покладене просте повторення первинної кодової комбінації з подальшим доповненням кодової комбінації перевірочним елементом, який отримують як доповнення до суми елементів первинної кодової комбінації до значення потужності алфавіту коду (основи коду). Значення перевірочного елемента визначається різницею між та сумою значень всіх елементів первинної кодової комбінації за .
Код дозволяє виправити тільки всі однократні помилки. При цьому місце помилки визначається в декодері простим співставленням інформаційної та повтореної частин прийнятої кодової комбінації. Незбіг значень елементів у деякому розряді вказує на помилку у цьому розряді. Для визначення, в якій частині кодової комбінації виникла помилка: в інформаційній чи повтореній, виконують перевірку за кожної частини комбінації окремо. При цьому у перевірку за повинен входити і перевірочний елемент, який міститься у кінці кодової комбінації. При перевірці отримуємо контрольний елемент, значення якого при відсутності помилки буде дорівнювати нулю, а при виникненні однократної помилки – буде відрізнятися від нуля.
При виникненні помилки в інформаційній частині прийнятої кодової комбінації її виправляють. Виправлене значення інформаційного елемента отримують як різницю за між спотвореним інформаційним елементом та одержаним при перевірці у декодері контрольним елементом.
Надмірність коду .
Приклад. Інформаційний код 102, . Кодуємо – . Вносимо помилку: , .
Узагальнений код Хеммінга УКХ є найбільш поширеним з недвійкових кодів такого класу. Код призначений для виправлення однократних помилок у термінах недвійкової арифметики.
Перевірочна матриця УКХ має розмір :
де r – кількість перевірочних елементів,
n – довжина кодової комбінації,
i – номер рядка,
j– номер стовпця.
Стовпці матриці повинні бути ненульовими і різними та, крім того, всі вони повинні мати однакову першу ненульову компоненту . Оскільки відповідає умові , число її можливих значень дорівнює . Звідси, виключивши нульовий вектор-стовпець, отримаємо число вектор-стовпців у матриці (отже і максимальну довжину кодової комбінації)
. (10.1)
При побудові матриці виявляється, що перших її вектор-стовпців, кожний з яких містить єдину ненульову компоненту , утворюють діагональну підматрицю розміру .
Ця обставина вказує на зручні позиції для розміщення перевірочних елементів у комбінації. Загалом макет кодової комбінації можна подати як:
, (10.2)
де , – -ічні відповідно інформаційні та перевірочні елементи кодової комбінації.
З розв’язання фундаментального матричного рівняння систематичних кодів
відносно перевірочних елементів , випливає
, (10.3)
де – транспонований вектор .
Показане у (10.2) розміщення перевірочних елементів не є єдино можливим, але воно забезпечує мінімальний обсяг обчислень при кодуванні та декодуванні. При цьому вираз (10.3) дає оптимальний алгоритм кодування. Кодовий вектор (10.2) поелементно передається у канал зв’язку у вигляді певних сигналів, де він може бути спотворений завадою. Фізичні явища процесу спотворення сигналів не мають значення, тому що з алгебраїчних міркувань його доцільно подати як , де – спотворений кодовий вектор на виході тракту передачі; – вектор помилки з єдиною ненульовою компонентою е (у припущенні однієї помилки).
Процедура декодування містить у собі, як перший крок, за аналогією з двійковим кодом Хеммінга, обчислення -компонентного перевірочного синдрому:
,
.
Вектор являє собою помножений на значення помилки () стовпець перевірочної матриці , що відповідає позиції спотвореного елемента у кодовому векторі . Його називають локатором місця помилки. Оскільки всі вектор-стовпці у мають першу ненульову компоненту, що дорівнює , то у перша ненульова компонента завжди буде . Це обумовлює другий крок процедури декодування – визначення значення помилки:
(10.4)
З визначення випливає третій крок процедури декодування – знаходження локатора місця помилки:
, (10.5)
тобто кожна компонента вектора ділиться на значення помилки .
На четвертому кроку процедури декодування шляхом упорядкованого перебору стовпців перевірочної матриці і порівняння кожного з локатором по збігу визначають позицію спотвореного елемента у кодовій комбінації.
П’ятим і останнім кроком декодування є виправлення помилки, яке виконується відніманням за значення помилки від значення спотвореного елемента, знайденого у за його локатором . Після цього спотворений елемент у прийнятій кодовій комбінації замінюють результатом віднімання і, виключивши перевірочні елементи, подають одержувачу інформаційну частину кодової комбінації.
Надмірність коду .
Зазначимо, що недвійкові коди прийнято ділити на дві великі групи:
Найбільший практичний інтерес має окремий випадок таких кодів при , символи якого мають інформаційну ємність біт і можуть бути співставленні з усіма -розрядними двійковими числами. Вибір впливає на визначення операцій додавання, віднімання, множення і ділення, які використовуються у процедурах кодування і декодування. Якщо основа – просте число, зручно використати апарат обчислень за модулем простого числа. Якщо ж , то необхідно звернутися до алгебраїчного апарату обчислень за модулем незвідного полінома. Символи коду при цьому ставлять у відповідність елементам скінченого поля порядку , а саме .
У табл. 10.1.1 та 10.1.2 наведені результати операцій додавання та множення у скінченому полі . Операцію додавання двох елементів виконано як порозрядне додавання за їх двійкових еквівалентів з подальшим записом цього числа у вісімковому поданні. Операція множення виконується як множення двох поліномів, що відповідають елементам поля, за модулем незвідного полінома степеня (у даному разі ).
Таблиця 10.1.1 Таблиця 10.1.2
|
+ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
|
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
3 |
2 |
5 |
4 |
7 |
6 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
2 |
2 |
3 |
0 |
1 |
6 |
7 |
4 |
5 |
2 |
0 |
2 |
4 |
6 |
3 |
1 |
7 |
5 |
|
|
3 |
3 |
2 |
1 |
0 |
7 |
6 |
5 |
4 |
3 |
0 |
3 |
6 |
5 |
7 |
4 |
1 |
2 |
|
|
4 |
4 |
5 |
6 |
7 |
0 |
1 |
2 |
3 |
4 |
0 |
4 |
3 |
7 |
6 |
2 |
5 |
1 |
|
|
5 |
5 |
4 |
7 |
6 |
1 |
0 |
3 |
2 |
5 |
0 |
5 |
1 |
4 |
2 |
7 |
3 |
6 |
|
|
6 |
6 |
7 |
4 |
5 |
2 |
3 |
0 |
1 |
6 |
0 |
6 |
7 |
1 |
5 |
3 |
2 |
4 |
|
|
7 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
7 |
0 |
7 |
5 |
2 |
1 |
6 |
4 |
3 |
Наприклад, перевіримо, що із табл. 10.1.2.
, , ,
|
x3x2 |
x3x1 |
||
|
x3 x1 |
1 |
||
|
x2x1 |
Перевіримо, що із табл. 10.1.1.
, , , .
3/6=3∙6-1=3∙3=5, 2/4=5
Для виконання операцій додавання і множення у скінченому полі зручніше користуватися адитивною та мультиплікативною формами запису десяткового числа, які подані у табл. 10.1.3. Операції виконуються на основі модульного полінома , який задає розширювальне рівняння або .
В першій колонці цієї таблиці наведені елементи поля у десятковому поданні (ці номерні записи можна розглядати як імена окремих елементів).
У другій колонці наведено подання елементів поля у формі двійкового вектора (сукупності коефіцієнтів двійкового поліному – остачі від ділення на ) з природнім розподілом вагів 23 22 21 20.
У третій колонці наведено мультиплікативну форму подання елементів поля у вигляді степенів примітивного елемента2 . Нагадаємо, що степені від до примітивного елемента відповідають усім ненульовим елементам поля , тобто .
Можна замінити будь-який високий степінь на такий, що не перевищує , якщо мати на увазі, що 15=0=1, 16=, 17=2, 18=3, . . .
Таблиця 10.1.3
|
Елементи |
Подання у формі вектора 23 22 21 20 |
Адитивна форма a3b2c1d0, a,b,c,d{0,1} у базисі 3210 |
|
|
0 |
0 0 0 0 |
0 = 1/ |
0 |
|
1 |
0 0 0 1 |
0= 1 |
1 |
|
2 |
0 0 1 0 |
1 |
|
|
3 |
0 0 1 1 |
4 |
1 |
|
4 |
0 1 0 0 |
2 |
2 |
|
5 |
0 1 0 1 |
8 |
2 1 |
|
6 |
0 1 1 0 |
5 |
2 |
|
7 |
0 1 1 1 |
10 |
2 1 |
|
8 |
1 0 0 0 |
3 |
3 |
|
9 |
1 0 0 1 |
14 |
3 1 |
|
10 |
1 0 1 0 |
9 |
3 |
|
11 |
1 0 1 1 |
7 |
3 1 |
|
12 |
1 1 0 0 |
6 |
3 2 |
|
13 |
1 1 0 1 |
13 |
3 2 1 |
|
14 |
1 1 1 0 |
11 |
3 2 |
|
15 |
1 1 1 1 |
12 |
3 2 1 |
Виконаємо, наприклад, множення елементів 13 та 15 поля GF(16) за допомогою степенів :
1315 = 1312=25= 1015= 101 = 10= 7.
Задача10.2.7
Закодувати вісімковим узагальненим кодом Хеммінга кодову комбінацію вісімкового первинного коду , . Показати процес виправлення однократної помилки.
Розв’язання. У відповідності з виразом (10.1) при та маємо , що недостатньо для побудови коду з . При максимальна довжина коду . Таким чином, вибираємо і матриця має розміри .
Довільно надаємо значення і будуємо матрицю :
Кодова комбінація закодована УКХ буде мати вигляд . Обчислюємо значення перевірочних елементів за алгоритмом (10.3). Множення і додавання виконуємо у відповідності з табл. 10.1.1 та 10.1.2:
Тобто одержуємо значення . Таким чином, у канал з кодера подається вектор .
Виправимо однократну помилку. Для цього припустимо, що вектор прийнятої кодової комбінації має вигляд .
Декодування починаємо з обчислення перевірочного синдрому :
Тобто синдром є таким .
Значення помилки, у відповідності із співвідношенням (10.4): (оберненим до 2 числом є 5, оскільки із табл. 10.2 маємо ), а локатор помилки, згідно із (10.5):
.
Виконуючи упорядковане перебирання стовпців матриці і порівнюючи їх з локатором , виявляємо по збігу, що було спотворено дванадцятий елемент у комбінації , значення якого . Для виправлення помилки до значення прийнятої кодової комбінації додамо значення помилки і одержимо вірне значення: . Після заміни спотвореного значення елемента на істинне, видаємо одержувачу повідомлення інформаційну частину виправленої кодової комбінації: .
Код Ріда-Соломона (РС) застосовується для передачі інформації по каналах з високою інтенсивністю завад, за яких виникають помилки кратністю два і більше та пачки помилок. Коди РС розглядають як такий випадок кодів БЧХ, коли поле локаторів збігається з полем його елементів. Тобто, якщо поле елементів БЧХ-коду має окремих елементів (потужність поля ), а поле його локаторів має елементів і є -розширенням поля елементів , то у РС-коді і елементи коду і їх локатори знаходяться у одному полі і належать . Інакше кажучи, РС-код – це вироджена форма БЧХ-коду, у якого .
Довжина блока РС-коду , де – потужність алфавіту (основа) коду.
РС-код, як і БЧХ-код, може задаватися твірною чи перевірочною матрицями або твірним чи перевірочним поліномами. Найбільш поширений спосіб побудови РС-коду на основі твірного поліному . Перевірочну матрицю часто використовують для вивчення деяких властивостей РС-коду та його зв’язку з систематичними кодами.
Твірний поліном коду РС, що виправляє помилок, є добутком мінімальних поліномів для спектру елементів з , де – кількість перевірочних елементів у блоці коду:
, (10.6)
де – спектр твірних коренів поліному .
Степінь такого поліному дорівнює числу перевірочних елементів .
Для спрощення побудови РС-коду часто вибирають та одержують:
(10.7)
Перевірочний поліном РС-коду одержують як частку від ділення на .
Мінімальна кодова відстань РС-коду .
Надмірність коду .
Найбільш просто коди РС реалізуються для алфавіту потужністю , тобто коли .У цьому випадку операції віднімання співпадають з операціями додавання, тому скрізь можна знак замінити на , зокрема у виразах (10.6) та (10.7).
Декодування кодів РС виконується у відповідності з загальними принципами циклічних кодів. У разі виправлення помилок одержують значення локаторів , що відповідають спотвореним елементам, і значення помилок для кожного спотвореного елемента. Виправлення помилок виконують відніманням від значення відповідного елемента значення помилки. Для полегшення виконання операцій результати додавання і множення у полі наведені табл. 10.3.
Задача 10.2.8
Закодувати кодом Ріда-Соломона, що виправляє дві помилки, комбінацію шістнадцяткового первинного коду довжиною .
Розв’язання. Для зручності у подальших обчисленнях запишемо комбінацію шістнадцяткового коду у вигляді
та
Як випливає з умови задачі, потужність алфавіту коду . Тоді РС-код може мати довжину . Кількість перевірочних елементів .
Твірний поліном коду РС, що виправляє помилок, є добутком мінімальних поліномів (10.6):
Приймаємо ; тоді твірний поліном буде мати вигляд:
Скориставшись для виконання розрахунків табл. 10.1.3, одержимо:
Кодування первинної кодової комбінації виконуємо за одним з правил побудови циклічного коду: :
Таким чином, кодова комбінація коду РС буде мати вигляд:
або
Недвійкові ітеративні коди мають більш високу здатність виявляти помилки у порівнянні з аналогічними двійковими ітеративними кодами. При зростає обсяг інформації, що передається, завдяки тому, що кількість інформації, яка міститься в одному елементі кодової комбінації, визначається потужністю алфавіту коду. У таких ітеративних кодах для кодування по рядках і стовпцях використовують недвійкові коди з перевіркою за . Виявлення помилок виконується за аналогією з двійковим кодом – порівнянням перевірочних елементів кожного рядка (стовпця), поданих з каналу до декодера елементів коду, та одержаних у декодері шляхом обчислень.
Виправлення спотвореного елемента виконують наступним чином. Якщо не виконується перевірка для -го рядка та -го стовпця, то елемент, що знаходиться на перетинанні -го рядка та -го стовпця, замінюють елементом, який є сумою за даного прийнятого елемента (помилкового) та перевірочного елемента -го рядка (або -го стовпця), який був одержаний у декодері.
При виникненні декількох помилок у одному рядку (стовпці), помилки виправляють послідовно для тих стовпців (рядків), де вони є поодинокими.
Задача 10.2.9
Закодувати вісімковим ітеративним кодом, що виправляє однократні помилки, інформаційну послідовність
Визначити надмірність коду та показати процес виправлення однократної помилки.
Розв’язання. Для того, щоб ітеративний код виправляв однократні помилки, досить для кодування по стовпцям і рядкам використати код з перевіркою за , тобто у даному разі – за .
Запишемо задану інформаційну послідовність у вигляді матриці та закодуємо кожний стовпець та кожний рядок одержаної матриці кодом з перевіркою за :
|
2 |
4 |
0 |
7 |
3 |
|
4 |
3 |
5 |
1 |
3 |
|
4 |
4 |
6 |
7 |
3 |
|
0 |
2 |
1 |
5 |
0 |
|
6 |
3 |
4 |
4 |
Таким чином кодована послідовність вісімкового ітеративного коду буде мати вигляд: .
Надмірність коду .
Припустимо, що при передачі по каналу зв’язку у кодованій послідовності виникла одна помилка і до декодера надходить така послідовність: . Для виявлення та виправлення помилки у декодері кодована послідовність, що надійшла з каналу, записується у вигляді матриці по 5 елементів у кожному рядку і виконується перевірка кожного рядка та кожного стовпця матриці за :
|
2 |
4 |
0 |
7 |
3 |
0 |
|
4 |
3 |
5 |
1 |
3 |
0 |
|
4 |
7 |
6 |
7 |
3 |
5 |
|
0 |
2 |
1 |
5 |
0 |
0 |
|
6 |
3 |
4 |
4 |
7 |
0 |
|
0 |
5 |
0 |
0 |
0 |
В результаті перевірки бачимо, що для третього рядка та другого стовпця перевірка не дає нульового результату. Це говорить про те, що на перетинанні третього рядка та другого стовпця знаходиться спотворений елемент.
Виправлення спотвореного елемента виконують таким чином. У зв’язку з тим, що не виконується перевірка для 3-го рядка і 2-го стовпця, елемент, що знаходиться на перетинанні 3-го рядка і 2-го стовпця, замінюють елементом, який є сумою за прийнятого (помилкового) елемента та перевірочного елемента 3-го рядка (або 2-го стовпця), який був одержаний у декодері, тобто . Таким чином, виправлена послідовність на виході декодера буде мати вигляд: .
Висновки
Контрольні питання
Задачі
10.3.1. Згідно з варіантом, поданим в таблиці 10.3.1, побудувати недвійкові первинні коди з алфавітом потужності q при заданій довжині коду n: на перестановки, на певне число розміщень, на певне число сполучень, на всі сполучення та змінно-якісний.
Таблиця 10.3.1
|
№ варі-анта |
Потуж-ність алфавіту коду, q |
Довжина недвійкового коду, n |
||||
|
На перестановки |
На певне число розміщень |
На певне число сполучень |
На всі сполучення |
Змінно-якісний |
||
|
1 |
3 |
3 |
3 |
3 |
3 |
4 |
|
2 |
4 |
4 |
2 |
2 |
2 |
3 |
|
3 |
4 |
4 |
3 |
3 |
3 |
4 |
|
4 |
5 |
5 |
2 |
2 |
2 |
3 |
|
5 |
5 |
5 |
3 |
3 |
3 |
4 |
|
6 |
6 |
6 |
2 |
2 |
2 |
3 |
|
7 |
6 |
6 |
3 |
3 |
3 |
4 |
|
8 |
7 |
7 |
2 |
2 |
2 |
3 |
|
9 |
8 |
8 |
2 |
2 |
2 |
3 |
|
10 |
8 |
8 |
3 |
3 |
3 |
4 |
10.3.2. Згідно з варіантом, поданим в таблиці 10.3.2, закодувати комбінацію А недвійкового коду на всі сполучення з алфавітом потужності q недвійковими кодами, що виявляють помилки: з перевіркою за mod q та з простим повторенням. Показати процес виявлення однократної помилки, визначити та порівняти надмірності цих кодів.
Таблиця 10.3.2
|
№ варіанта |
Потужність алфавіту коду, q |
Комбінація первинного коду, A |
|
1 |
4 |
1032 |
|
2 |
5 |
4310 |
|
3 |
6 |
34512 |
|
4 |
7 |
21563 |
|
5 |
8 |
032745 |
|
6 |
9 |
674831 |
|
7 |
10 |
5479802 |
|
8 |
12 |
479А0В1 |
|
9 |
14 |
391А2С84 |
|
10 |
16 |
D17А2EFВ |
10.3.5. Згідно з варіантом поданим в таблиці 10.3.5, закодувати недвійковим кодом: з багатократним повторенням комбінацію А первинного змінно-якісного коду з алфавітом потужності q. Визначити надмірність одержаного коду та показати процес виправлення будь-якої помилки кратності s.
Таблиця 10.3.5
|
№ варіанта |
Потужність алфавіту коду, q |
Кратність помилки, s |
Комбінація первинного коду, А |
|
1 |
3 |
2 |
1012 |
|
2 |
4 |
2 |
0130 |
|
3 |
5 |
2 |
42301 |
|
4 |
7 |
1 |
20235436 |
|
5 |
8 |
1 |
32310167 |
10.3.6. Згідно з варіантом поданим в таблиці 10.3.6, закодувати недвійковим кодом з простим повторенням та перевіркою за mod q комбінацію А первинного змінно-якісного коду з алфавітом потужності q. Визначити надмірність одержаного коду та показати процес виправлення будь-якої однократної помилки.
Таблиця 10.3.6
|
№ варіанта |
Потужність алфавіту коду, q |
Комбінація первинного коду, А |
|
1 |
3 |
2012 |
|
2 |
4 |
02131 |
|
3 |
6 |
14510215 |
|
4 |
7 |
012354362 |
|
5 |
8 |
202310176 |
10.3.7. Згідно з варіантом, поданим в таблиці 10.3.7, закодувати узагальненим кодом Хеммінга (УКХ) з алфавітом потужності q та ненульовою компонентоюкодову комбінацію первинного коду А. Показати процес виправлення однократної помилки.
Таблиця 10.3.7
|
№ варіанта |
Потужность алфавіту коду, q |
Ненульова компонента, |
Комбінація первинного коду, А |
|
1 |
8 |
2 |
7501032 |
|
2 |
8 |
3 |
4741310 |
|
3 |
8 |
4 |
345021 |
|
4 |
8 |
5 |
21563 |
|
5 |
8 |
6 |
0327450145 |
|
6 |
8 |
7 |
5012674831 |
|
7 |
16 |
1 |
А0В5471 |
|
8 |
16 |
2 |
479А0В6 |
|
9 |
16 |
4 |
31А2СЕ |
|
10 |
16 |
1 |
D13457А2EFВ |
10.3.8. Згідно з варіантом, поданим в таблиці 10.3.8, закодувати кодом Ріда-Соломона, що виправляє помилки кратності s, комбінацію шістнадцяткового первинного коду Q(0,F) з k інформаційними елементами.
Таблиця 10.3.8
|
№ варіанта |
Потужність алфавіту коду, q |
Кратність помилки, s |
Кількість інформаційних елементів, k |
Комбінація первинного коду Q(0,F) |
|
1 |
16 |
1 |
11 |
D3AB1221384 |
|
2 |
16 |
1 |
7 |
F38D110 |
|
3 |
16 |
1 |
8 |
1100EFAA |
|
4 |
16 |
1 |
9 |
CС5BAF301 |
|
5 |
16 |
1 |
10 |
BB335711A0 |
|
6 |
16 |
2 |
11 |
229ABB11244 |
|
7 |
16 |
2 |
8 |
100215AF |
|
8 |
16 |
2 |
9 |
369АВ0206 |
|
9 |
16 |
2 |
10 |
32745АС821 |
|
10 |
16 |
3 |
11 |
AА0CС142670 |
10.3.9. Згідно з варіантом, поданим в таблиці 10.3.9, закодувати недвійковим ітеративним кодом з алфавітом потужності q, що виправляє однократні помилки, інформаційну послідовність А. Визначити надмірність коду та показати процес виправлення однократної помилки.
Таблиця 10.3.9
|
№ варіанта |
Потужність алфавіту коду, q |
Комбінація первинного коду А |
|
1 |
3 |
1012010121021210 |
|
2 |
4 |
0101231010212020 |
|
3 |
4 |
103013201212 |
|
4 |
5 |
0213042412403042 |
|
5 |
6 |
0320102543202045 |
|
6 |
7 |
6431010201234560 |
|
7 |
8 |
5471020345010202 |
|
8 |
8 |
7012023457603201 |
|
9 |
16 |
391А2С840В1D |
|
10 |
16 |
479А0В1D17А2EFВ0 |
2 Элемент, степени которого пробегают все ненулевые элементы поля, называется примитивным элементом