ДОСЛІДЖЕННЯ КОРЕКТУЮЧИХ ВЛАСТИВОСТЕЙ ЦИКЛІЧНИХ КОДІВ.. Методичні вказівки з Методи кодування інформації. Робота № 203568

ДОСЛІДЖЕННЯ КОРЕКТУЮЧИХ ВЛАСТИВОСТЕЙ ЦИКЛІЧНИХ КОДІВ.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра Телекомунікацій

Інформація про роботу

Рік:

2015

Тип роботи:

Методичні вказівки

Предмет:

Методи кодування інформації

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра “Телекомунікації” ДОСЛІДЖЕННЯ КОРЕКТУЮЧИХ ВЛАСТИВОСТЕЙ ЦИКЛІЧНИХ КОДІВ Методичні вказівки до лабораторної роботи № 8 з курсу «Методи кодування інформації» для студентів базового напрямку «Телекомунікації» Львів 2001 “Дослідження коректуючих властивостей циклічних кодів”. Методичні вказівки до лабораторної роботи № 8 з курсу “Методи кодування інформації” для студентів базового напрямку 0924 - “Телекомунікації”. - Львів 2001. – 7 с. Автори: доцент Коваль Б.В. ст. викладач Чайковський І.Б. Рецензенти: професор, д.т.н. Оганесян А.Г. доцент, к.т.н. Волочій Б.Ю. У лабораторній роботі досліджуються властивості циклічних кодів в режимі виправлення багатократних некорельованих помилок. Методичні вказівки затверджено на засіданні кафедри “Телекомунікації” Національного університету “Львівська політехніка” 04.04.2001 р., протокол № 8. Мета роботи: Практично дослідити коректуючі властивості циклічних кодів в режимі виправлення некорельованих помилок. Теоретичні відомості. Циклічні коди - це різновид систематичних кодів, тому вони мають усі їх властивості. Простота реалізації схем кодування/декодування (апаратна реалізація) забезпечила циклічним кодом широке застосування на практиці. При розгляді циклічних кодів, КК зручно представляти у вигляді полінома степені (n - 1) , де n - кількість розрядів КК: EMBED Equation.2 . У двійковій системі числення, яку ми розглядаємо, EMBED Equation.2 можуть приймати два значення - 0 та 1. Наприклад, двійкова послідовність 01001 може бути записана у вигляді полінома EMBED Equation.2 . Таким чином дії над КК можна звести до дій над многочленами. Арифметичні операції над поліномами. а) додавання: проводиться додавання по модулю два коефіцієнтів при однакових степенях х: EMBED Equation.2 б) віднімання: тотожне операції додавання. в) множення: проводиться по звичайному правилу перемножування степеневих функцій, однак отримані коефіцієнти додаються по модулю два: EMBED Equation.2 Очевидно, що множити і додавати можна " в рядок", зводячи (сумуючи по модулю 2) відповідні коефіцієнти. г) ділення: виконується по правилах ділення степеневих функцій, при цьому операції віднімання замінюються додаванням по модулю 2: EMBED Equation.2 Бачимо, що результати, отримані у прикладах п.п. в) і г) співпадають. Вказані вище операції над поліномами, для скорочення запису, можна записувати у двійковій формі. Тоді приклади, наведені в п.п. а) - г) матимуть вигляд: а) 1101 б) 1101 г) 10111  11  11 х 11  11  1101 1110 1101 11  1101 11 10111 11 11 0 Кодова комбінація циклічного кода (n, k) може бути отримана двома способами: 1. Множимо многочлен С(х) степені (k - 1), що відповідає k інформаційним розрядам, на породжуючий неприводимий поліном P(x) степені (r), де r = n - k - кількість перевірочних розрядів КК: F(x) = C(x)P(x) Многочлен F(x) степені (n - 1) = k + r - 1 визначає отриману КК, що відповідає C(x). 2. Множимо многочлен Q(x) степені (k - 1), що відповідає k інформаційним розрядам, на одночлен хr , де r = n - k - кількість перевірочних розрядів КК, і додаємо до цього добутку залишок R(x), що отриманий у результаті ділення Q(x)хr на породжуючий неприводимий поліном P(x) степені r: F(x) = Q(x)хr + R(x) Многочлен F(x) степені (n - 1) = k + r - 1 визначає отриману КК, що відповідає Q(x). Залишок R(x) визначається з виразу: EMBED Equation.2 Тут С(х) - частка від ділення, многочлен степені (k - 1) , так само як і Q(x). Степінь многочлена R(x) не може перевищувати (r - 1), тому що P(x)-степені r. Якщо помножимо обидві частини рівняння (3) на Р(х), перенесемо R(x) в ліву частину, то отримаємо (порівняти з (1)) F(x) = Q(x)хr + R(x) = C(x)P(x) Отже, ми отримали ту саму КК F(x) двома способами. C(x) та Q(x) - різні інформаційні многочлени степені (k - 1). Однак при побудові циклічного коду другим способом (2) розміщення інформаційних символів у всіх КК чітко впорядковане - вони займають k старших розрядів КК, а решта r = n - k розрядів - перевірочні ( контрольні). Найважливішою задачею побудови циклічних кодів, є вибір породжуючого полінома, що задовільняє наперед заданим умовам. В першу чергу вибираємо кількість k інформаційних розрядів, виходячи з потрібної кількості робочих комбінацій: EMBED Equation.2 . Далі визначається мінімальна довжина КК n , що забезпечує виявлення або виправлення помилок заданої кратності. Для циклічних кодів (ЦК) ця проблема зводиться до пошуку потрібного полінома Р(х) степені r = n - k . В основу побудови циклічних кодів покладено використання неприводимих многочленів. Неприводимим називається многочлен, який не може бути записаний у вигляді добутку многочленів нижчих степенів, тобто такий многочлен ділиться лише сам на себе або на 1 і не ділиться без остачі на жоден інший многочлен (аналог простого числа). Двочлен хn + 1 ділиться без остачі на неприводимий многочлен. Неприводимі многочлени в теорії циклічних кодів відіграють роль породжуючих поліномів. Їх пошук та побудова є складною задачею комбінаторики, однак зараз існують в літературі довідкові таблиці, у яких приведені неприводимі поліноми різних степенів. Так, наприклад, у довіднику [4] можна знайти всі НП до 9-ої степені включно (табл. 1). Таблиця 1. Породжуючий поліном Р(х) приймає участь у побудові кожної робочої КК (див. (2) - (4)), тому комбінація кода ділиться на Р(х) без залишка. Але без залишка діляться лише ті многочлени (КК), які є робочими, тобто породжуючий поліном дозволяє вибрати дозволені КК з усіх можливих. Якщо ж при діленні прийнятої КК циклічного кода на Р(х) буде отриманий залишок відмінний від нуля, значить виникла помилка. Отже, залишки від ділення в цьому випадку є індикаторами помилок ЦК. Але ці залишки ще не вказують безпосередньо на місце помилки в прийнятій КК. Таким чином відбувається процес виявлення помилок. Для виправлення помилок у прийнятих кодових комбінаціях циклічного коду використовують приведений нижче алгоритм: Нехай циклічний код, побудований на основі породжуючого поліному Р(х), дозволяє виправляти помилки кратності tвипр і менше. Якщо прийнята КК містить у собі не більше, ніж tвипр помилок, то для виявлення і виправлення помилкових розрядів проводять наступні операції: 1) прийняту КК ділять на Р(х); 2) підраховують кількість одиниць у залишку (вагу залишку ). Якщо   tвипр, тоді прийняту КК додають до модулю 2 з отриманим залишком. Сума дає виправлену КК, stop. Якщо ж  > tвипр, тоді переходять до п. 3. 3) проводять циклічний зсув прийнятої КК вліво на q розрядів, ділення зсунутої комбінації на Р(х) і підрахунок ваги залишку. Цей пункт виконується послідовно для всіх значень q від 1 до n до того часу, поки вага залишку  не стане меншою чи рівною tвипр; додаємо по модулю 2 до КК, зсунутої на q розрядів вліво, її залишок. Отриману комбінацію зсуваємо на q розрядів вправо. Таким чином ми отримуємо передану КК з виправленими помилками. Завдання На основі лабораторного макету дослідити практично властивості і характеристики циклічних кодів, що виправляють помилки. Навчитись визначати породжуючі поліноми циклічних кодів. Порядок виконання роботи Ознайомитись з теоретичною частиною. Запустити програму Luchana.exe: в меню вибрати “Файл”, “Тестовий файл”. У вікні, що з’явиться, вказати назву тестового файлу і його розмір. Цей файл можна автоматично заповнити або одиничними символами (вибравши перемикач “Заповнити одиницями”), або нульовими символами (вибравши перемикач “Заповнити нулями”). Натиснути кнопку “Ok”; в меню вибрати “Режим відображення”, “Одиночні помилки”. У вікні, що з’явиться, натиснути кнопку “Кодування”, “Циклічні кодери”; вибрати тестовий вхідний файл для кодування, задати назву вихідного файлу; користуючись таблицею 2, задати значення параметрів n (довжина кодової комбінації), r (кількість перевірочних розрядів), k (кількість інформаційних розрядів), і tвипр (кратність виправлення помилки), задати породжуючий поліном самим безпосередньо в стрічці редагування. Вибрати перемикач “Закодувати” і натиснути кнопку “Ok”; Натиснути кнопку “Канал”. В меню “Вхідний файл” вказати назву закодованого файлу. В меню “Вихідний файл” вказати назву вихідного файлу; в розділі “Тип каналу” вибрати перемикач “Симетричний”; в розділі “Тип помилки” вибрати перемикач “Одиночні”; натиснути кнопку “Параметри”. У вікні, що з’явиться, ввести значення імовірності одиночної помилки. Натиснути кнопку “Ok”; Натиснути кнопку “Передати”. натиснути кнопку “Декодування”, “Циклічні кодери”; в меню “Вхідний файл” вказати назву файла, який пройшов через канал зв’язку. В меню “Вихідний файл” вказати назву вихідного файлу; вибрати значення параметрів, які були задані при кодуванні, натиснути кнопку “Порахувати параметри”. Встановити перемикач в положення “Декодувати”, натиснути кнопку “Ok”; 4. Підрахувати (вручну або з допомогою раніше розробленої програми) кількість помилкових блоків у вихідному файлі. Визначити імовірність невиявленої помилки. Повторити для інших значень імовірності одиночної помилки, заданих викладачем. Повторити кодування, внесення помилок, декодування та розрахунки для всіх породжуючих поліномів з табл. 2. Порівняти та зробити висновки. Таблиця 2. Рекомендації: Для наглядності найзручніше використовувати вхідні тестові файли, які заповнені нулями. Для зручності користування файли рекомендується називати систематично. Наприклад, 111, 222, 333, ..., ХХХ , ... , де Х- номер контрольної точки макету. Для наглядного прогляду процесу проходження файлу по імітаційній моделі зв’язку є можливість проглянути файл в побітовому режимі, викликавши відповідно програму прогляду файлів. Для цього можна натиснути кнопку 1, 2, і т.д., які знаходяться у вікні “Модель телекомунікаційної системи”. Література Цымбал В.П. Теория информации и кодирование. - 1992. Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования: Учебник для вузов, 2-е изд., перераб. и доп. -1986. Кларк Д., Кейн Д. Кодирование с исправлением ошибок в системах цифровой связи. - 1987. Кодирование информации (двоичные коды). Справочник/ Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. и др. - 1978. Коваль Б.В. Конспект лекцій з курсу „Методи кодування інформації” для студентів базового напрямку „Телекомунікації”. – Львів, 2001. Підписано до друку 14.05.2001. Папір офсетний. Друк офсетний. Умов.-друк. арк. 0,44. Формат 60х84 1/16. Наклад 100 прим. Зам. 1021. Віддруковано в НВМ Поліграфічного технікуму УАД 79008, м. Львів, пл. Митна, 1

Методичні вказівки Методи кодування інформації

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись