1. лінійних блокових Коди
Приклади попереднього розділу показують, що завдання побудови хороших кодів з заданим кодовою відстанню є досить складною, і при досить великій довжині кодового слова не може бути вирішена повним перебором навіть із залученням засобів сучасної обчислювальної техніки. Для скорочення перебору при побудові хороших кодів використовується апарат загальної алгебри. Більшість кодів, використовуваних на практиці, є лінійними кодами.
1.1. Структура лінійних блокових кодів
Нагадаємо, що булево простір B n. B =, являє собою безліч двійкових векторів довжини n. операція Å складання по модулю 2 є груповий операцією, і безліч B n являє собою лінійний простір з операцією Å і множенням на скаляр з безлічі.
Лінійним двійковим або груповим кодом називається підпростір лінійного простору B n.
Таким чином, лінійний код є непорожня множина двійкових слів довжини n, званих кодовими словами. таке, що сума двох кодових слів є кодовим словом. У будь-якому лінійному коді нульове слово 0 = 0. 0 виконує роль нуля. Більш того, в лінійному двійковому коді кожне слово протилежно самому собі, так як c Å c = 0. 0 для будь-якого cÎB n. Ми далі в основному будемо розглядати лінійні двійкові коди. Тому слово «двійковий» будемо опускати, і операцію Å складання по модулю 2 будемо називати просто операцією додавання і позначати +.
Приклад. Розглянемо безліч V =. Безпосередньою перевіркою можна переконатися, що сума будь-яких двох слів безлічі є елементом множини, т. Е. V - лінійний код.
Нагадаємо, що в лінійному (n, k) - коді число k є розмір блоку інформаційних символів, який потім, при кодуванні, перетворюється в блок з n символів, де n> k. Додані n-k символів називають перевірочними символами. Зауважимо, що не завжди можна сказати, які символи є інформаційними, а які - перевірочними.
Наприклад, в лінійному (5,3) -код V = базисом є безліч. Вектор 01010 представляється у вигляді лінійної комбінації 01010 = 1 × 10011 + 1 × 11001 + 1 × 11100. Безпосередньою перевіркою можна переконатися, що кодова відстань дорівнює 3.
У загальному випадку для знаходження кодового відстані кодові слова порівнюються один з одним. Однак, в лінійному коді кодове відстань збігається з мінімальною вагою ненульового кодового слова.
Теорема 1.1. Кодова відстань лінійного коду одно мінімальній вазі ненульового кодового слова.
Доведення. Нехай відстань коду збігається з відстанню між кодовими словами x і y. Так як V лінійний код, то x + y = z теж належить коду V; т. о. dV = w (z). Так як нульове слово належить коду V. то код не містить ненульових слів ваги менше dV.
Доведення. Кожне кодове слово є лінійна комбінація базисних кодових слів. Число різних лінійних комбінацій одно, т. Е. | V | ≤ 2 k. Дві лінійні комбінації з різними коефіцієнтами не збігаються, так як базисні вектори лінійно незалежні. Тому | V | = 2 k.