Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ КОРЕКТУЮЧИХ ВЛАСТИВОСТЕЙ ЦИКЛІЧНИХ КОДІВ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра Телекомунікацій
Інформація про роботу
Рік:
2001
Тип роботи:
Методичні вказівки
Предмет:
Методи кодування інформації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Кафедра “Телекомунікації”
ДОСЛІДЖЕННЯ КОРЕКТУЮЧИХ ВЛАСТИВОСТЕЙ ЦИКЛІЧНИХ КОДІВ
Методичні вказівки до лабораторної роботи № 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
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора