Матричне подання циклічних кодів

Для формування рядків породжувальної матриці за першим способом утворення циклічного коду беруть комбінації простого k-розрядного коду G(х), що містять одиницю в одному розряді. Ці комбінації збільшуються на х^n-k, визначається залишок R(х) від ділення отриманого добутку х^n-kG(х) на утворюючий поліном і записується відповідний рядок матриці у вигляді суми добутку х^n-kG(х) і залишку R(х). При цьому породжувальна матриця Р_n,k подається двома підматрицями – інформаційною U_k і додатковою Н_р:

.

Інформаційна підматриця U_k, являє собою квадратну одиничну матрицю з кількістю рядків і стовпців, рівною k. Додаткова підматриця Н_р містить р = п - k стовпців і k рядків і утворена залишками R(х).

Породжувальна матриця дозволяє одержати k комбінацій коду. Інші комбінації утворюються підсумовуванням за модулем два рядків породжувальної матриці у всіх можливих поєднаннях.

При другому способі утворення циклічного коду породжувальна матриця P_n,k формується шляхом множення утворюючого полінома Р(х) степеня = n - k на одночлен x^k-1 наступних k-1 зсувів отриманої комбінації.

Вибір утворюючого полінома

При побудові циклічного коду спочатку визначається число інформаційних розрядів k за заданим об’ємом коду. Потім знаходиться найменша довжина кодових комбінацій n, що забезпечує виявлення або виправлення помилок заданої кратності. Ця проблема зводиться до перебування потрібного утворюючого полінома Р(х).

Як уже відзначалося раніше, степінь утворюючого полінома повинен дорівнювати числу перевірних розрядів .

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

Найбільше число залишків, що дорівнює 2-1 (крім нульового), може забезпечити тільки многочлен порядка степеня , що не ділиться ні на який інший многочлен.

Відомо, що двочлен типу (хⁿ + 1) = (х^2z-1 + 1), у розкладанні якого як співмножник повинен входити утворюючий многочлен, має ту властивість, що він є спільним кратним для усіх без винятку незвідних поліномів степеня n і розкладається на множники з усіх незвідних поліномів степеня 2, які діляться без залишку на число z.

Найпростішим циклічним кодом є код, що забезпечує виявлення однократних помилок. Вектору однократної помилки відповідає одночлен xⁱ, степінь котрого i може приймати значення від 1 до п. Для того щоб могла бути виявлена помилка, одночлен xⁱ не повинен ділитися на утворюючий поліном Р(х). Серед незвідних многочленів, що входять у розкладання двочлена хⁿ + 1, є багаточлен найменшого степеня х + 1. Таким чином утворюючим поліномом даного коду є двочлен Р(х) = х + 1. Залишок від ділення будь-якого многочлена на х + 1 може приймати тільки два значення: 0 і 1. Отже, при будь-якому числі інформаційних розрядів необхідний тільки один перевірний розряд. Значення символу цього розряду забезпечує парність числа одиниць у кодовій комбінації.

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

Для побудови циклічного коду, що виправляє однократні або виявляє дворазові помилки, необхідно, щоб кожній одиничній помилці відповідав свій розпізнавач, тобто залишок від ділення многочлена прийнятої комбінації на утворюючий многочлен. Оскільки кількість можливих однократних помилок дорівнює п, а незвідний многочлен степеня може дати 2 - 1 ненульових залишків, то необхідною умовою виправлення будь-якої одиничної помилки є виконання нерівності

.

Звідси знаходять степінь утворюючого полінома

(5.6)

і загальну довжину п кодової комбінації.

Оскільки утворюючий многочлен Р(х) повинен входити як співмножник в розкладання двочлена (хⁿ + 1) = (х^2z-1 + 1), то використовуючи відзначені раніше властивості цього двочлена, а також умову (5.6), можна вибрати утворюючий поліном.

Однак не всякий мнгочлен степеня , що входить у розкладання двочлена хⁿ + 1, може бути використаний як утворюючий поліном. Необхідно, щоб для кожної із п однократних помилок забезпечувався свій, відмінний від інших, залишок від розподілу прийнятої кодової комбінації на утворюючий поліном. Це буде мати місце за умови, якщо обраний незвідний многочлен степеня , будучи дільником двочлена хⁿ + 1, не входить у розкладання ніякого іншого двочлена х^і + 1, степінь якого і < п.

Утворюючі поліноми кодів, які здатні виправляти помилки будь-якої кратності, можна визначати, користуючись таким правилом Хеммінга.

1. За заданим числом інформаційних розрядів k визначається число перевірних розрядів , необхідне для виправлення однократних помилок, і знаходиться утворюючий поліном.

2. Розглядаючи отриманий (n, k)-код і некоректуючий n-розрядний код визначають додаткові розряди для забезпечення виправлення однієї помилки в цьому коді і знаходять відповідний утворюючий поліном.

3. Повторюється дана процедура стільки разів, поки не буде отриманий код, що виправляє незалежні помилки до даної кратності включно.

Закодувати просту інформаційну групу G(х) = 1011 циклічним кодом, що забезпечує виявлення дворазових або усунення однократних помилок.

Розв’язання. За заданою кількістю інформаційних символів k = 4

визначаємо значність коду. Користуючись співвідношенням (5.6) і табл. 5.1, отримаємо n = 3,2.

Для побудови циклічного коду необхідно вибрати утворюючий поліном Р(х) степеня = n – k = 3, що повинен входити як співмножник, а для розкладання двочлена хⁿ + 1= х^2z-1 - 1. В нашому випадку цей двочлен має вигляд х⁷+1. Складові його співмножники повинні бути незвідними поліномами, степені яких є дільниками числа z = 3. Отже, співмножниками двочлена х⁷+ 1 повинні бути незвідні поліноми першого і третього степенів. Користуючись таблицями незвідних поліномів отримаємо

.

Вибираємо як утворюючий поліном співмножник

.

Кодування здійснюємо першим способом. Для цього вихідну кодову комбінацію G(х) множимо на x^n-k=x³

.

Визначаємо залишок R(х) від розподілу х^n-k G(х) на утворюючий багаточлен Р(х):

Залишок R(x) = х².

Отже, поліном F(х) циклічного коду буде мати вигляд

.

Отримане повідомлення циклічним кодом Р*(х) = х⁶+ х⁴ + х³ + х². Перевірити декодуванням наявність помилок у прийнятій комбінації, якщо утворюючий поліном Р(х) == х³ + х² +1.

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

.

Залишок від розподілу R(х) = 0. Отже, комбінація прийнята без перекручувань.

 

Отримана комбінація P*(х) = х⁶ + х⁴ + х² + 1, закодована циклічним кодом. Утворюючий поліном Р(х) = х3 + х2 + 1. Перевірити наявність помилок у кодовій комбінації.

Розв’язання. Ділимо поліном отриманої комбінації на утворюючий поліном

.

залишок – R(х) = х^2 0. Отже, комбінація прийнята з помилками.

Побудувати породжувальну матрицю циклічного коду при n = 7;
k = 4. Утворюючий поліном Р(х) = х² + х + 1.

Розв’язання. Оскільки k = 4, інформаційна підматриця має вигляд

.

Для одержання першого рядка додаткової підматриці множимо перший рядок інформаційної підматриці на x³. Ділимо на утворюючий поліном, тобто виконуємо операції . Залишок від цих операцій 011 складає перший рядок додаткової підматриці. Аналогічно визначаємо інші рядки додаткової підматриці. Додаткова підматриця має вигляд:

.

Остаточно одержимо таку породжувальну матрицю:

.

Для побудови породжувальної матриці другим способом перший рядок матриці одержуємо шляхом множення утворюючого полінома на
x^k-1: Р(х)·x^k-1 =1011 · 1000 = 1011000. Наступні рядки матриці отримаємо шляхом циклічного зміщення отриманої комбінації. Таким чином породжувальна матриця

.

 

Згорткові коди.

Згорткові коди відносяться до безперервних рекурентних кодів. Кодове слово є згорткою відгуку лінійної системи (кодера) на вхідну інформаційну послідовність. Тому згорткові коди є лінійними, для яких сума будь-яких кодових слів також є кодовою послідовністю.

Розглянемо згортковий код з швидкостями вигляду , де - деяке натуральне число.Послідовність символів такого згорткового коду складається з елементарних блоків завдовжки , причому символів поточного блоку (що займають реальний час, що відповідає одному інформаційному біту) є лінійною комбінацією поточного інформаційного біта і m попередніх. Значення m визначає пам'ять коду, а параметр m + 1 називається довжиною кодового обмеження. Якщо один (наприклад, перший) з символів поточного блоку повторює поточний інформаційний біт, код називається систематичним.

Кодер загорткового коду містить тактований регістр памяті для збереження визначеного числа інформаційних символів і перетворювач вхідної інформаційної послідовності у вихідну кодову послідовність. Структурна схема кодера ЗК (7.5) зображена на рисунку 1.3.

 

Рис.1.3 – Структурна схема кодера

 

Послідовність кодування детально розписана в таблиці 1.

Таблиця 1 - Процес кодування послідовності інформаційних бітів 01101000

 

Способи задання згорткових кодів багато в чому збігаються з використовуваними для лінійних блокових. Одним з основних є опис згорткового коду набором многочленів. Кожен многочлен встановлює закон формування одного з символів в групі і має міру, що не перевищує m. Ненульові коефіцієнти полінома, що створюються, прямо вказують, які з інформаційних символів (включаючи поточний і m попередніх) входять в лінійну комбінацію, що дає даний символ коду.

Кодові грати цього коду показані на мал. 1.1. При його складанні враховано, що кодер містить пам'ять у вигляді дворозрядного регістра. Кожному з чотирьох можливих станів цього регістра відповідає один з чотирьох вузлів решітки. Тому лівий символ в позначенні вузла дорівнює останньому інформаційному біту, вже записаному в регістр. При записі в регістр чергового інформаційного символу регістр міняє стан на одне з двох сусідніх. Цей перехід позначений ребрами грат. Порядок вузлів вибраний таким, що при нульовому поточному інформаційному символі (а=0) перехід в наступний стан відповідає верхньому ребру, а при = 1 - нижньому.

Рисунок 1.1 - Кодові грати

 

Кожній інформаційній послідовності відповідає певний шлях на кодових гратах і кодова послідовність. Наприклад, вхідним інформаційним бітам 01100 відповідає кодове слово 00 11 01 01 11, якому відповідає на мал. 1.1 шлях, відмічений жирною лінією.

Відомий ряд алгоритмів декодування згортальних кодів. У практичних системах і, зокрема в мобільному зв'язку, як правило, використовується алгоритм Вітербі, що відрізняється простотою реалізації при помірних довжинах кодового обмеження.

Алгоритм Вітербі реалізує оптимальне (максимально правдоподібне) декодування як рекурентний пошук на кодовой гратах шляху, найближчого до послідовності, що приймається. На кожній ітерації алгоритму Вітербі зіставляються два шляхи, що ведуть в даний стан (вузол грат). Найближчий з них до прийнятої послідовності зберігається для подальшого аналізу. Нехай передається нульове кодове слово, а в каналі виникла трикратна помилка, так що прийнята послідовність має вигляд 10 10 00 00 10 00... 00.... Результати пошуку найближчої дороги після прийому 14 елементарних блоків показані на рисунку 1.2.

 

Рисунок 1.2 - Приклад роботи алгоритму Вітербі

 

 

Імпульсно-кодова модуляція

І́мпульсно-ко́дова модуля́ція ---- використовується для оцифровки аналогових сигналів перед їхньою передачею. Практично всі види аналогових даних (відео, голос, музика, дані телеметрії, віртуальні мири) допускають застосування імпульсно-кодовій модуляції.

 

Щоб одержати на вході каналу зв'язку (передавальний кінець) ІК-модульований сигнал з аналогового, амплітуда аналогового сигналу вимірюється через рівні проміжки часу. Кількість оцифрованих значень у секунду (або швидкість оцифрування) кратна максимальній частоті (Гц) у спектрі аналогового сигналу. Миттєве обмірюване значення аналогового сигналу округляється до найближчого рівня з декількох заздалегідь певних значень. Цей процес називається квантуванням, а кількість рівнів завжди береться кратним ступеню двійки, наприклад, 8, 16, 32 або 64. Номер рівня може бути відповідно представлений 3, 4, 5 або 6 бітами. Таким чином, на виході модулятора виходить набір бітів (0 або 1).

 

На прийомному кінці каналу зв'язку демодулятор перетворює послідовність бітів в імпульси з тим же рівнем квантування, що використав модулятор. Далі ці імпульси використовуються для відновлення аналогового сигналу.

 

Різновидами ІКМ є:

Диференціальна (або дельта) імпульсно-кодова модуляція (ДІКМ) кодує сигнал у вигляді різниці між поточним і попереднім значенням. Для звукових даних такий тип модуляції зменшує необхідну кількість біт на відлік приблизно на 25%.

Адаптивна ДІКМ (АДІКМ) є різновидом ДІКМ, що змінює рівень кроку квантування, що дозволяє ще більше зменшити вимоги до смуги пропускання при заданому відношенні сигналу і шуму.

 

Импульсно-кодовая модуляция

 

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

 

При кодовой модуляции необходимо передать числа, выражающие величину квантованных отсчетов. Для этого можно воспользоваться двоичным кодом. Числа, подлежащие передаче, надо записать в двоичной системе счисления – это и даст необходимые кодовые комбинации. При помощи n - значных двоичных чисел можно представить чисел. Благодаря квантованию количество чисел, подлежащих передаче, сводится до конечной величины. Если принять шаг квантования за единицу, то будет означать наибольшее квантованное значение. Количество знаков в двоичной кодовой комбинации равно. Если n – не целое, то оно округляется до ближайшего целого числа. На рис.3 показаны преобразования аналогового сигнала (а) в АИМ (б) и ИКМ (в) для n = 4.

Рис. 3

 

При выборе шага квантования (или числа N) следует учитывать два фактора. С одной стороны, увеличение числа ступеней квантования увеличивает точность передачи сигнала, с другой – требует удлинения кодовой комбинации (n). Так для телефонной передачи установлено, что удовлетворительное качество передачи достигается при , т.е. при семизначном коде.

 

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

 

заменяет отношение сигнал – шум.

 

Пусть число уровней квантования равно N. Будем передавать каждое из N значений n-значным кодовым числом, составленным из импульсов, квантованных на m уровней (АИМ). Общее число возможных комбинаций равно . Очевидно, что . Пусть шкала уровней симметрична относительно нуля, т. е. разрешенными являются уровни:

 

Если все уровни равновероятны, средняя мощность сигнала равна

Отсюда шаг квантования равен

 

откуда

 

Таким образом, при неизменных мощностях сигнала и помехи выгодно уменьшать основание кода. Наименьшее значение m равно 2 (двоичный код), что соответствует ИКМ. В этом случае т.е. введенная величина совпадает с обычным определением отношения сигнал – помеха.

 

В обычной АИМ N=m >>1, и в этом случае

 

 

Следовательно, ИКМ дает выигрыш в отношении сигнал – помеха в раз.

 

Какой же ценой достигается этот выигрыш? Если при АИМ за каждый тактовый интервал (отсчет) передается один импульс, то при ИКМ за тот же интервал должны быть переданы n импульсов. При неизменной скважности каждый из этих n импульсов в n раз короче (см. рис. 3), а, следовательно, ширина спектра сигнала в n раз больше, чем ширина спектра сигнала АИМ. Таким образом, за увеличение отношения сигнал – помеха мы расплачиваемся расширением полосы.