Дискретна математика алгоритми

Загальні відомості про принципи побудови циклічних кодів

Широке поширення на практиці отримав клас лінійних кодів, які називаються циклічними. Дана назва походить від основного властивості цих кодів, а саме, якщо деяка кодова комбінація належить циклічним кодом, то комбінація, отримана циклічної перестановкою вихідної комбінації (циклічним зрушенням), також належить даному коду:

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

Ці властивості використовуються при побудові кодів, кодують і декодер, а також при виявленні і виправленні помилок.

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

В основі побудови циклічних кодів лежить операція ділення переданої кодової комбінації на який породжує не приводиться поліном ступеня r. Залишок від ділення використовується при формуванні перевірочних розрядів. При цьому операції ділення передує операція множення, що здійснює зрушення вліво k -розрядної інформаційної кодової комбінації на r розрядів.

При декодуванні прийнятої n -розрядної кодової комбінації знову проводиться розподіл на породжує поліном.

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

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

Нехай загальне число біт в блоці одно n. з них корисну інформацію несуть в собі m біт, тоді в разі помилки є можливість виправити s біт. Залежність s від n і m для кодів можна знайти [6] в таблиці:

n. загальне число біт

m. число корисних біт

s. число виправляються біт

Подання кодової комбінації у вигляді многочлена

Опис циклічних кодів і їх побудова зручно проводити за допомогою многочленів (або полиномов). Запис комбінації у вигляді полінома знадобилася для того, щоб відобразити формалізованим способом операцію циклічного зсуву вихідної кодової комбінації. Так, n -елементную кодову комбінацію можна описати поліномом (n - 1) ступеня, у вигляді:

A n -1 (x) = a n -1 x n -1 + a n -2 x n -2 + ... + a 1 x + a 0.

де a i =, причому a i = 0 відповідають нульовим елементам комбінації, a i = 1 - ненульовим.

Запишемо поліноми для конкретних 4-елементних комбінацій:

1101 ↔ A 1 (x) = x 3 + x 2 + 1
1010 ↔ A 2 (x) = x 3 + x

Операції додавання і віднімання виконуються за модулем 2. Вони є еквівалентними і асоціативними:

Операція поділу є звичайним поділом многочленів, тільки замість віднімання використовується додавання по модулю 2:

Циклічний зсув кодової комбінації

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

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

Припустимо, задана вихідна кодова комбінація і відповідний їй поліном:

a (x) = a n x n -1 + a n -1 x n -2 + ... + a 2 x + a 1

Помножимо a (x) на x:

a (x) · x = a n x n + a n -1 x n -1 + ... + a 2 x 2 + a 1 x

Так як максимальний ступінь x в кодової комбінації довжиною n не перевищує (n - 1), то з правої частини отриманого виразу для отримання вихідного полінома необхідно відняти a n (x n - 1). Віднімання a n (x n - 1) називається взяттям залишку по модулю (x n - 1).

Зрушення вихідної комбінації на i тактів можна представити таким чином: a (x) · x i - a n (x n - 1), тобто множенням a (x) на x i і взяттям залишку по модулю (x n - 1). Взяття залишку необхідно при отриманні многочлена ступеня, більшою чи рівною n.

породжує поліном

Ідея побудови циклічних кодів базується на використанні непріводімих многочленів. Непріводімим називається многочлен, який не може бути представлений у вигляді добутку многочленів нижчих ступенів, т. Е. Такий многочлен ділиться тільки на самого себе або на одиницю і не ділиться ні на який інший многочлен. На такий многочлен ділиться без залишку двочлен x n + 1. Непріводімие многочлени в теорії циклічних кодів грають роль утворюють поліномів.

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

p (x)
p (x) · x - C 2 (x n - 1)
p (x) · x 2 - C 3 (x n - 1)
...
p (x) · x m -1 - C m (x n - 1)

де p (x) - вихідна кодова комбінація, на базі якої отримані всі інші (m - 1) базові комбінації, C i = 0 або C i = 1 ( «0», якщо результуюча ступінь полінома p (x) · xi не перевищує (n - 1), «1», якщо перевершує).

Комбінація p (x) називається породжує (породжує, генераторної) комбінацією. Для побудови циклічного коду досить вірно вибрати p (x). Потім всі інші кодові комбінації виходять такими ж, як і в груповому коді.

Породжує поліном повинен відповідати таким вимогам:

  1. p (x) повинен бути ненульовим;
  2. вага p (x) не повинен бути менше мінімального кодового відстані: v (p (x)) ≥ d min;
  3. p (x) повинен мати максимальну ступінь k (k - число надлишкових елементів в коді);
  4. p (x) повинен бути дільником поліному (x n - 1).

Виконання умови 4 призводить до того, що всі робочі кодові комбінації циклічного коду набувають властивість подільності на p (x) без залишку. З огляду на це, можна дати інше визначення циклічного коду. Циклічний код - код, все робочі комбінації якого діляться на який породжує без залишку.

Для визначення ступеня породжує полінома можна скористатися виразом r ≥ log2 (n +1), де n - розмір переданого пакета за раз, т. Е. Довжина споруджуваного циклічного коду.

Приклади породжують полиномов, можна знайти [5] в таблиці:

r. ступінь полінома

P (x), який породжує поліном

111100111, 100011101, 101100011

Алгоритм отримання дозволеної кодової комбінації циклічного коду з комбінації простого коду

Нехай заданий поліном P (x) = a r -1 x r + a r -2 x r -1 + ... + 1, що визначає коригувальну здатність коду і число перевірочних розрядів r. а також вихідна комбінація простого k -елементного коду у вигляді многочлена A k -1 (x).

Потрібно визначити дозволену кодову комбінацію циклічного коду (n. K).

  1. Множимо многочлен вихідної кодової комбінації на x r.

A k -1 (x) · x r

  • Визначаємо перевірочні розряди, що доповнюють вихідну інформаційну комбінацію до дозволеної, як залишок від ділення отриманого в попередньому пункті твори на породжує поліном:

    A k -1 (x) · x r / P r (x) → R (x)

  • Остаточно дозволена кодова комбінація циклічного коду визначиться так:

    A n -1 (x) = A k -1 (x) · x r + R (x)

    Для виявлення помилок в прийнятій кодовій комбінації досить поділити її на виробляє поліном. Якщо прийнята комбінація - дозволена, то залишок від ділення буде нульовим. Ненульовий залишок свідчить про те, що прийнята комбінація містить помилки. По виду залишку (синдрому) можна в деяких випадках також зробити висновок про характер помилки, її місцезнаходження і виправити помилку.

    Приклад. Нехай потрібно закодувати комбінацію виду 1101, що відповідає A (х) = х 3 + х 2 + 1.

    Визначаємо число контрольних символів r = 3. З таблиці візьмемо багаточлен P (х) = х 3 + х + 1, т. Е. 1011.

    Помножимо A (х) на х r.

    A (x) · x r = (x 3 + x 2 + 1) · x 3 = x 6 + x 5 + x 3 → 11010000

    Розділимо отримане твір на який утворює поліном g (х):

    A (x) · xr / P (x) = (x 6 + x 5 + x 3) / (х 3 + х + 1) = х 3 + х 2 + х + 1 + 1 / (х 3 + х + 1) → 1111 + 001/1011

    При розподілі необхідно враховувати, що віднімання проводиться по модулю 2. Залишок підсумовуємо з h (х) · х r. В результаті отримаємо закодоване повідомлення:

    F (x) = (x 3 + x 2 + 1) · (x 3 + x + 1) = (x 3 + x 2 + 1) · x 3 + 1 → 1101001

    В отриманій кодової комбінації циклічного коду інформаційні символи A (х) = 1101, а контрольні R (х) = 001. Закодоване повідомлення ділиться на який утворює поліном без залишку.

    Алгоритм визначення помилки

    Нехай маємо n -елементние комбінації (n = k + r) тоді:

    1. Отримуємо залишок від ділення Е (х) відповідного помилку в старшому розряді [1000000000], на який породжує поліном P r (x):
  • Ділимо отриманий поліном Н (х) на P r (x) і отримуємо поточний залишок R (x).
  • Порівнюємо R 0 (x) і R (x).
    • Якщо вони рівні, то помилка сталася в старшому розряді.
    • Якщо немає, то збільшуємо ступінь прийнятого полінома на x і знову проводимо ділення:

    H (x) · x / P r (x) = R (x)

  • Знову порівнюємо отриманий залишок з R 0 (x).
    • Якщо вони рівні, то помилки в другому розряді.
    • Якщо немає, то множимо Н (х) · х 2 і повторюємо ці операції до тих пір, поки R (x) не дорівнює R 0 (x).

    • Помилка буде в розряді, що відповідає числу, на яке підвищена ступінь Н (х), плюс один.

    Наприклад: H (x) · x 3 / P r (x) = R 0 (x)

    Французький вчений А. Хоквінгем (1959 рік) і американці Р. К. Боуз і Д. К. Рой-Чоудхурі (1960) знайшли великий клас кодів, що забезпечує довільне мінімальна кодова відстань d min ≥ 5. Вони отримали назву БЧХ ( Боуза-Чоудхурі-хоквінгема). Породжують поліноми для таких кодів в залежності від пред'явлених до них вимог, можна знайти [7] в таблиці:

    Де n - загальне число елементів, m - число інформаційних елементів, k - число надлишкових елементів (n = m + k).

    Процедура побудови коду БЧХ по заданих M і d min.

    1. по d min знайти значення, при якому забезпечується необхідне число інформаційних елементів m при мінімальній надмірності k min;
    2. знайти в таблиці відповідний породжує поліном;
    3. якщо d min парне, помножити знайдений поліном на (x + 1);
    4. якщо m табл >> m заданий. то можна перейти до скороченим циклічного коду, викреслюючи в породжує матриці вихідного коду з параметрами m табл. k min (m табл - m заданий) стовпців зліва і стільки ж рядків зверху.

    визуализатор

    Подивитися визуализатор одного способу побудови циклічного коду можна тут.

    огляд джерел

    У книгах [1], [2] і на сайтах [3], [4] представлені теоретичні відомості, способи побудови, а також приклади використання циклічних кодів.

    На сайтах [5], [6], [7], в основному, представлені практичні дослідження, їх деякі результати, цікаві залежності і таблиці по циклічним кодами.

    література

    Є пара заміток по помилках.

    >>> Таблиця БЧХ, взята з наведеного вище сайту.

    25 31 11 5 11 5423325 +101100010011011010101

    швидше за все містить помилку в першому числі - замість 25 повинно бути 20 (за визначенням, k = колічество_біт_в_поліноме - 1, а також має виконуватися умова k + m = n).