Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ ПРОЦЕСУ ВИПРАВЛЕННЯ НЕКОРЕЛЬОВАНИХ ПОМИЛОК КОДАМИ БЧХ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра Телекомунікацій
Інформація про роботу
Рік:
2001
Тип роботи:
Методичні вказівки
Предмет:
Методи кодування інформації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Кафедра “Телекомунікації”
ДОСЛІДЖЕННЯ ПРОЦЕСУ ВИПРАВЛЕННЯ НЕКОРЕЛЬОВАНИХ ПОМИЛОК КОДАМИ БЧХ
Методичні вказівки до лабораторної роботи № 9
з курсу «Методи кодування інформації»
для студентів базового напрямку «Телекомунікації»
Львів 2001
“Дослідження процесу виправлення некорельованих помилок кодами БЧХ”. Методичні вказівки до лабораторної роботи № 9 з курсу “Методи кодування інформації” для студентів базового напрямку 0924 - “Телекомунікації”. - Львів 2001. – 11 с.
Автори: доцент Коваль Б.В.
ст. викладач Чайковський І.Б.
Рецензенти: професор, д.т.н. Оганесян А.Г.
доцент, к.т.н. Волочій Б.Ю.
У лабораторній роботі досліджуються коректуючі властивості кодів БЧХ в режимі виправлення некорельованих помилок.
Методичні вказівки затверджено на засіданні кафедри “Телекомунікації” Національного університету “Львівська політехніка” 04.04.2001 р., протокол № 8.
Мета роботи
Дослідити коректуючі властивості кодів БЧХ в режимі виправлення некорельованих помилок. Навчитися знаходити породжуючі поліноми кодів БЧХ, що забезпечують необхідну коректуючу здатність.
Теоретичні відомості
Циклічні коди - це різновид систематичних кодів, тому вони мають усі їх властивості. Простота реалізації схем кодування/декодування (апаратна реалізація) забезпечила циклічним кодом широке застосування на практиці.
При розгляді циклічних кодів, кодову комбінацію (КК) зручно представляти у вигляді полінома степені (n - 1) , де n - кількість розрядів КК:
EMBED Equation.2 .
У двійковій системі числення, коефіцієнти EMBED Equation.2 можуть приймати лише два значення - 0 та 1.
Наприклад, двійкова послідовність 01001 може бути записана у вигляді полінома
EMBED Equation.2 .
Таким чином дії над КК можна звести до дій над многочленами.
БЧХ коди представляють собою різновид циклічних кодів, які дозволяють виправляти багатократні некорельовані помилки.
Примітивний БЧХ-код, який виправляє t помилок, - це блоковий код довжиною EMBED Equation.2 .
Розглянемо один із способів знаходження породжуючого полінома для кодів БЧХ. Цей поліном визначається по заданій кодовій відстані і довжині КК:
EMBED Equation.2 ;
де m = 2, 3, 4, 5,... .
Кількість перевірочних і інформаційних розрядів кода можна оцінити з допомогою формул:
EMBED Equation.2
Коди БЧХ мають непарне значення dmin.
Породжуючий поліном БЧХ-кода є найменшим спільним кратним (НСК) так званих мінімальних поліномів mi(x), де i = 1,3,5,..., (d - 2),
EMBED Equation.2
Нагадаю, НСК декількох многочленів є многочлен найнижчої степені, який ділиться на кожен з них без остачі( аналог - спільний знаменник в дробах).
Тут значення mi(x) приведемо у вісімковій системі числення (для скорочення запису) - кожна вісімкова цифра = двійкова тріада.
Таблиця 1. Список породжуючих мнолгочленів для двійкових БЧХ-кодів.
Для знаходження породжуючого полінома з EMBED Equation.2 розрядів і з кодовою відстанню d необхідно виписати з таблиці всі значення мінімальних поліномів, що відповідають заданому m , до порядка (d - 2) включно.
Якщо даний порядок в таблиці відсутній, треба взяти найближчий менший. Р(х) представляє собою добуток всіх цих поліномів.
Приклад. Необхідно побудувати код довжиною n = 15 ( m = 4 ) з d = 7.
Породжуючий поліном буде EMBED Equation.2
По нашій таблиці знаходимо:
EMBED Equation.2 ;
EMBED Equation.2 ;
EMBED Equation.2 ;
Перемножимо отримані мінімальні поліноми в результаті отримаємо EMBED Equation.2
БЧХ-коди мають непарне значення dmin. При бажанні dmin можна збільшити на 1, використавши породжуючий поліном, що рівний добутку породжуючого полінома БЧХ-кода на (х + 1). Отримаємо модифікований БЧХ-код з парним значенням dmin. При цьому r зростає на 1, а n залишається незмінним ( k зменшиться на 1).
Приклад: для попереднього прикладу
EMBED Equation.2
EMBED Equation.2 При розгляді БЧХ-кодів відмітимо наступні закономірності.
Кількість кодів, що відрізняються по своїй коректуючій здатності і мають спільну довжину КК EMBED Equation.2 , на 2 одиниці менша кількості всіх неприводимих многочленів, на які розкладається двочлен EMBED Equation.2 . Згадайте приклад розкладу
EMBED Equation.2
що ми провели раніше. Тут кількість неприводимих многочленів = 5, а отже кількість циклічних кодів для n = 15 буде 3.
Ще однією важливою властивістю БЧХ-кода є співвідношення між найбільшим значенням dmin, що може бути досягнуто для заданого m :
EMBED Equation.2
При m = 4 (n = 15) dmax = 7.
Ще одне співвідношення:
EMBED Equation.2
для заданого m і при d = dmax
При m = 4 (n = 15) і dmax = 7 k = 4 + 1 = 5.
Коди БЧХ складають великий клас кодів, які легко будуються, з будь-якою довжиною блока і швидкістю. Важливість цих кодів забезпечується не тільки гнучкістю вибору їх параметрів, але й тим, що при довжинах блока біля декількох сотень багато з них є оптимальними середь всіх відомих кодів з тими ж довжиною і швидкістю.
Найважливішою задачею побудови циклічних кодів є вибір породжуючого полінома, що забезпечує задану мінімальну кодову відстань d.
В першу чергу вибираємо кількість k інформаційних розрядів, виходячи з потрібної кількості робочих комбінацій: EMBED Equation.2 . Далі визначається мінімальна довжина КК n , що забезпечує виявлення або виправлення помилок заданої кратності. Для циклічних кодів (ЦК) ця проблема зводиться до пошуку потрібного полінома Р(х) степені r = n - k .
Кодова комбінація циклічного кода (n, k) може бути отримана двома способами:
1. Множимо многочлен С(х) степені (k - 1), що відповідає k інформаційним розрядам, на породжуючий неприводимий поліном P(x) степені (r), де r = n - k - кількість перевірочних розрядів КК:
F(x) = C(x)P(x) (1)
Многочлен 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) (2)
Многочлен F(x) степені (n - 1) = k + r - 1 визначає отриману КК, що відповідає Q(x).
Залишок R(x) визначається з виразу:
EMBED Equation.2 (3)
Тут С(х) - частка від ділення, многочлен степені (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) (4)
Отже, ми отримали ту саму КК F(x) двома способами. C(x) та Q(x) - різні інформаційні многочлени степені (k - 1).
Однак при побудові циклічного коду другим способом (2) розміщення інформаційних символів у всіх КК чітко впорядковане - вони займають k старших розрядів КК, а решта r = n - k розрядів - перевірочні ( контрольні).
Породжуючий поліном Р(х) приймає участь у побудові кожної робочої КК, тому комбінація кода ділиться на Р(х) без залишка. Але без залишка діляться лише ті многочлени (КК), які є робочими, тобто породжуючий поліном дозволяє вибрати дозволені КК з усіх можливих. Якщо ж при діленні прийнятої КК циклічного кода на Р(х) буде отриманий залишок відмінний від нуля, значить виникла помилка. Отже, залишки від ділення в цьому випадку є індикаторами помилок ЦК, тобто синдромом. Але ці залишки ще не вказують безпосередньо на місце помилки в прийнятій КК. Таким чином відбувається процес виявлення помилок.
Боуз і Чоудхурі довели, що для будь-яких цілих додатніх чисел m та tвипр. існує циклічний код розрядності
EMBED Equation.2
з кодовою відстанню
EMBED Equation.2
При цьому кількість перевірочних символів EMBED Equation.2 не перевищує значення EMBED Equation.2 , тобто
EMBED Equation.2
Такий код гарантовано виправляє помилки кратності tвипр. і менше, або виявляє помилки кратності 2tвипр чи менше.
Для виправлення помилок у прийнятих кодових комбінаціях циклічні БЧХ- коди використовують приведений нижче алгоритм:
Нехай циклічний БЧХ-код, побудований на основі породжуючого поліному Р(х), дозволяє виправляти помилки кратності tвипр і менше. Якщо прийнята КК містить у собі не більше, ніж tвипр помилок, то для виявлення і виправлення помилкових розрядів проводять наступні операції:
1) прийняту КК ділять на Р(х);
2) підраховують кількість одиниць у залишку (вагу залишку ). Якщо tвипр, тоді прийняту КК додають до модулю 2 з отриманим залишком. Сума дає виправлену КК, stop. Якщо ж > tвипр, тоді переходять до п. 3.
3) проводять циклічний зсув прийнятої КК вліво на q розрядів, ділення зсунутої комбінації на Р(х) і підрахунок ваги залишку. Цей пункт виконується послідовно для всіх значень q від 1 до n до того часу, поки вага залишку не стане меншою чи рівною tвипр;
4) додаємо по модулю 2 до КК, зсунутої на q розрядів вліво, її залишок. Отриману комбінацію зсуваємо на q розрядів вправо. Таким чином ми отримуємо передану КК з виправленими помилками.
Цей алгоритм декодування справедливий для циклічних кодів, побудованих з допомогою породжуючого полінома Р(х) як 1, так і 2 способом.
Приклад. (7,4) - циклічний код, що виправляє tвипр = 1 помилку, побудований на основі породжуючого полінома EMBED Equation.2 Інформаційне повідомлення 1001, закодоване 2 способом, матиме вигляд
1001000 1011
1011 1010
1000
1011
110
EMBED Equation.2
Нехай у 4-му розряді цієї КК виникла помилка, тобто прийнята КК має вигляд 1000110. Необхідно виправити помилку.
Рішення:
1. Ділимо прийняту КК на Р(х):
1000110 1011
1011 1011
1111
1011
1000
1011
11
2. Вага залишку =2 > tвипр = 1. Отже переходимо до п. 3.
q = 1
0001101 1011
1011 1
110 > tвипр
q =2 0011010 1011
1011 11
1100
1011
111 > tвипр
q =3 0110100 1011
1011 111
1100
1011
1110
1011
101 > tвипр
q =4 1101000 1011
1011 1111
1100
1011
1110
1011
1010
1011
1 =1= tвипр
Переходимо до п. 4.
4. 1101000
1
1101001
Проводимо циклічний зсув на q = 4 розряди вправо: Отже передана КК після виправлення 1 помилки матиме вигляд:
1001110 і співпадає з правильною.
Якщо в робочій КК виникла помилка кратності > tвипр ,то результат декодування (виявлення чи виправлення) може дати непередбачуваний результат.
Наприклад: (див. попередній приклад) помилка 2-ї кратності в робочій КК в першому і останньому розрядах:
1001110
0 1
Декодуємо:
0001111 1011 0001111
1011 1 100
100 =1 tвипр 0001011
Виправлена КК: 0001011 далека від справді переланої. Тут лише можна зробити висновок, що виникла помилка синдром-залишок 0 . Нагадаю, що цей код дозволяє виявляти помилки кратності EMBED Equation.2 .
Завдання.
На основі лабораторного макету дослідити практично властивості і характеристики БЧХ-кодів.
Навчитись визначати породжуючі поліноми для виправлення некорельованих помилок БЧХ-кодами.
Порядок виконання роботи.
Ознайомитись з теоретичною частиною. Розрахувати породжуючий поліном, основні параметри БЧХ-кодів, заданих викладачем.
Запустити програму Luchana.exe:
в меню вибрати “Файл”, “Тестовий файл”. У вікні, що з’явиться, вказати назву тестового файлу і його розмір. Цей файл можна автоматично заповнити або одиничними символами (вибравши перемикач “Заповнити одиницями”), або нульовими символами (вибравши перемикач “Заповнити нулями”). Натиснути кнопку “Ok”;
в меню вибрати “Режим відображення”, “Одиночні помилки”. У вікні, що з’явиться, натиснути кнопку “Кодування”, “Циклічні кодери”;
вибрати тестовий вхідний файл для кодування, задати назву вихідного файлу;
користуючись розрахунками п.1, задати значення параметрів n (довжина кодової комбінації), r (кількість перевірочних розрядів), k (кількість інформаційних розрядів), і tвипр (кратність виправлення помилки), задати породжуючий поліном самим безпосередньо в стрічці редагування. Вибрати перемикач “Закодувати” і натиснути кнопку “Ok”;
Натиснути кнопку “Канал”. В меню “Вхідний файл” вказати назву закодованого файлу. В меню “Вихідний файл” вказати назву вихідного файлу;
в розділі “Тип каналу” вибрати перемикач “Симетричний”;
в розділі “Тип помилки” вибрати перемикач “Одиночні”;
натиснути кнопку “Параметри”. У вікні, що з’явиться, ввести значення імовірності одиночної помилки. Натиснути кнопку “Ok”;
Натиснути кнопку “Передати”.
натиснути кнопочку “Декодування”, “Циклічні кодери”;
в меню “Вхідний файл” вказати назву файла, який пройшов через канал зв’язку. В меню “Вихідний файл” вказати назву вихідного файлу;
вибрати значення параметрів, які були задані при кодуванні, натиснути кнопку “Порахувати параметри”. Встановити перемикач в положення “Декодувати”, натиснути кнопку “Ok”;
Підрахувати (вручну або з допомогою раніше розробленої програми) кількість помилкових блоків у вихідному файлі. Визначити імовірність невиявленої помилки.
Повторити для інших значень імовірності одиночної помилки. Провести процеси кодування, внесення помилок, декодування та розрахунки для всіх заданих БЧХ кодів. Порівняти та зробити висновки.
Рекомендації:
Для зручності користування файли рекомендується називати систематично. Наприклад, 111-222-333-444-…., або AAA-BBB-CCC-DDD-….
Для наглядного прогляду процесу проходження файлу по емітаційній моделі зв’язку є можливість проглянути файл в побітовому режимі, викликавши відповідно програму прогляду файлів. Для цього можна натиснути кнопку 1, 2, і т.д., які знаходяться у вікні “Модель телекомунікаційної системи”.
Контрольні запитання.
Назвіть характеристики та властивості БЧХ-кодів.
Як визначається породжуючий поліном.
Поясніть процеси кодування та декодування БЧХ-кодів.
Як визначається кількість перевірочних розрядів, яка необхідна для кодування.
Що впливає на коректуючу здатність циклічних кодів.
Література
Цымбал В.П. Теория информации и кодирование. - 1992.
Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования: Учебник для вузов, 2-е изд., перераб. и доп. -1986.
Кларк Д., Кейн Д. Кодирование с исправлением ошибок в системах цифровой связи. - 1987.
Кодирование информации (двоичные коды). Справочник/ Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. и др. - 1978.
Коваль Б.В. Конспект лекцій з курсу „Методи кодування інформації” для студентів базового напрямку „Телекомунікації”. – Львів, 2001.
Додаток
Алгоритм кодування БЧХ-кодів
Початок
Задання параметрів
кодування: m , tвипр
Розрахунок
загального полінома
P(x)=p1(x)+p2(x)+…+pn(x)
Розрахунок
параметрів БЧХ-коду
r, n=2m-1, k=n-r
Зчитати k інформаційних
символа і дописати r нулів.
C(x)=Q(x)*xr
Визначення перевірочних
розрядів кодової комбінації
R(x)= C(x)/P(x)
Запис кодової комбінації
F(x)=C(x)+ R(x)
Кінець
Кінець файла?
Ні
Так
Алгоритм декодування БЧХ-кодів
Початок
Задання параметрів
декодування: m , tвипр
Розрахунок
загального полінома
P(x)=p1(x)+p2(x)+…+pn(x)
Розрахунок
параметрів БЧХ-коду
r, n=2m-1, k=n-r
Зчитати кодову комбінацію
F(x)
Запис кодової комбінації
КК=C(x)*R(x)
Кінець
Визначення інформаційних
розрядів кодової комбінації
C(x)= F(x)/P(x); R=0; q=0
R(x) 0; q++
Циклічний зсув кодової
комбінації вліво на
один розряд
Циклічний зсув кодової
комбінації вправо на
q розрядів
КК=C(x)*R(x)
Запис k інформаційних
декодованих розрядів
Так
Ні
Кінець файла?
Ні
Так
Підписано до друку 14.05.2001. Папір офсетний. Друк офсетний.
Умов.-друк. арк. 0,69. Формат 60х84 1/16. Наклад 100 прим. Зам. 1021.
Віддруковано в НВМ Поліграфічного технікуму УАД
79008, м. Львів, пл. Митна, 1
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора