Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Основні властивості циклічного коду й способи побудови

ЦИКЛІЧНІ КОДИ

ЛЕКЦІЯ 6

Мета –вивчення методів побудови циклічних кодів, алгоритм кодування, представлення комбінацій циклічних кодів у вигляді двійкових поліномів, операції над двійковими поліномами.

В лекції розглянуті наступні питання:

1. Основні властивості циклічних кодів і способи їх математичного опису.

2. Способи кодування і декодування циклічних кодів.

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

 

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

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

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

(1)

де - цифри даної системи числення (у двійковій системі 0 і 1).

Так, наприклад, двійкове семи розрядне число 1010101 може бути записане у вигляді полінома

(2)

Найбільший ступінь х у доданку з нульовим коефіцієнтом називається ступенем полінома.

Подання кодових комбінацій у формі (2) дозволяє звести дії над комбінаціями до дії над поліномами. При цьому додаванні поліномів зводиться до додавання по модулі «два» коефіцієнти при рівних ступенях змінної х, множення виконується за звичайним правилом перемножування ступеневих функцій, однак отримані при цьому коефіцієнти при рівних ступенях змінної х підсумовуються за модулем «два»; ділення здійснюється за правилами ділення ступеневих функцій, при цьому операції вирахування заміняються операціями підсумовування за модулем «два».

Подання комбінацій у формулах (1) і (2) зручно ще й тим, що згадана циклічна перестановка є результат простого множення даного полінома на х . Дійсно, якщо одна з кодових комбінацій виражається поліномом , то ново комбінація за рахунок циклічного зсуву буде

.

Однак в останньому виразі треба замінити на 1 і перемістити цей член на останню позицію.

Отже нова комбінація буде

.

Наприклад, циклічне зрушення кодової комбінації 1010101 може бути отриманий шляхом множення полінома (2) на х

.

Замінивши на 1, одержимо поліном

.

Відповідної кодової комбінації 0101011.

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

Циклічне зсув комбінації з одиницею в старшому n-му розряді рівносильний множенню відповідного багаточлена на х з одночасним вирахуванням з результату полінома або , тому що операції здійснюються за модулем «два». Отже, якщо в якості вихідного взяти деякий поліном Р(х), то процес одержання базових поліномів можна представити в наступному виді;

(3),

де -коефіцієнти, що приймають значення 1 при й значення 0 при .

При такому способі побудови базових поліномів поліном Р(х) називають утворюючим.

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

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

Таким чином утворюючий поліном Р(х) повинен задовольняти вимозі – він повинен бути дільником двочлена . Вибір Р(х) однозначно визначає циклічний код і його коригувальні властивості.

 


Читайте також:

  1. II. Основні закономірності ходу і розгалуження судин великого і малого кіл кровообігу
  2. Адвокатура в Україні: основні завдання і функції
  3. Аеродинамічні властивості колісної машини
  4. Аксіоматичний метод у математиці та суть аксіоматичної побудови теорії.
  5. Алгоритм побудови сітьових графіків.
  6. Алгоритми побудови дерев екстремальної ваги
  7. Амортизація основних засобів, основні методи амортизації
  8. Аналізатори людини та їхні властивості.
  9. Аналізатори людини та їхні властивості.
  10. Артеріальний пульс, основні параметри
  11. Атрибутивні ознаки і властивості культури
  12. Банківська система та її основні функції




Переглядів: 1358

<== попередня сторінка | наступна сторінка ==>
Контрольні запитання і завдання | Матричне подання циклічних кодів

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.