На головну

Матричне кодування. Групові коди.

При явному завданні схеми кодування в (m, n) -код слід вказати 2m кодових слів, що дуже неефективно.

Одним з економних способів опису схеми кодування є методика матричного кодування.

Раніше кожна схема кодування описувалася таблицями, які задають кодове слово довжини n для кожного вихідного слова довжини m. Для блоків великої довжини цей спосіб вимагає великого обсягу пам'яті і тому непрактичний. Наприклад, для (16, 33) -коду Потрібно 33 * 216 = 2 162 688 біт.

Набагато меншого обсягу пам'яті вимагає матричне кодування. нехай E матриця розмірності m ? n, Що складається з елементів eij, де i - Це номер рядка, а j - Номер стовпчика. Кожен з елементів матриці eij може бути або 0, або 1. Кодування реалізується операцією b = АЕ або  де кодові слова розглядаються як вектори, тобто як матриці-рядка
 розміру 1 ? n.

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

Матричні коди називають також лінійними кодами. для лінійних (N - r, n) -код З мінімальним відстанню Хеммінга d існує нижня межа Плоткина (Plotkin) для мінімальної кількості контрольних розрядів r
 при n? 2d - 1,

двійковий (m, n) -код називається груповим, якщо його кодові слова утворюють групу.

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

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

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

Це випливає з співвідношення d (bi, bj) = W (bi + bj).

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

Такі рядки помилок переводять одне кодове слово в інше.

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

Безліч всіх довічних слів a = a1 ... am довжини mутворює абелеву (комутативну) групу щодо порозрядного додавання.

нехай E - кодує m ? nматриця, у якої є m ?m-подматріца з відмінним від нуля визначником, наприклад, одинична. тоді відображення a > a Eпереводить групу всіх довічних слів довжини m в групу кодових слів довжини n.

Припустимо, що  тоді для  отримуємо

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

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

Групові коди зручно задавати за допомогою матриць, розмірність яких визначається параметрами k і n. Число рядків одно k, а число стовпців одно n = k + m.

Коди, породжувані цими матрицями, називаються (n, k) -код, а відповідні їм матриці породжують (утворюють, що виробляють).

 



 Теорема про коректує здатності кодів. |  Коди Хеммінга.

 Мінімізація в класі діз'юнктівних нормальних форм. |  Обчислення висловлювань і числення предикатів. |  обчислення предикатів |  Аксіоматичні теорії. Виводимість формул в обчисленні висловлювань. |  Теорема дедукції. Предикати, квантори. |  Формули логіки предикатів, їх еквівалентність, здійсненність і общезначімость. |  Аксіоми числення предикатів. |  поняття групи |  Циклічні групи. Групи підстановок. Кільця і ??поля |  Елементи теорії кодування. Подання про кодування. |

© um.co.ua - учбові матеріали та реферати