Завадостійке кодування. Поліноміальні коди
Алгоритми перешкодостійкого кодування процесом виявлення і виправлення одиничної помилки в циклічних кодах. Програмна реалізація процесу виявлення і виправлення помилок в циклічних кодах. Програма, що реалізує завдання засобами Borland C++Builder 6.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | украинский |
| Дата добавления | 24.04.2014 |
| Размер файла | 384,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
35
1
Курсова робота
на тему:
Завадостійке кодування. Поліноміальні коди
Студента
Носа Андрія Ігоровича
Анотація
Курсова робота присвячена вивченню алгоритмів перешкодостійкого кодування та програмній реалізації процесу виявлення і виправлення помилок в циклічних кодах. Розроблена програма, що реалізує завдання засобами Borland C++Builder 6.
Вступ
При передачі інформації по каналу зв'язку з перешкодами в прийнятих даних можуть виникати помилки. Якщо такі помилки мають невелику величину або виникають досить рідко, інформація може бути використана споживачем. При великому числі помилок отриманою інформацією користуватися не можна.
Для зменшення кількості помилок, що виникають при передачі інформації по каналу з перешкодами, може бути використане кодування в каналі, або перешкодостійке кодування [1-2].
Можливість використання кодування для зменшення числа помилок в каналі була теоретично показана К. Шенноном в 1948 році в його роботі "Математична теорія зв'язку". У ній було зроблено твердження, що якщо швидкість створення джерелом повідомлень (продуктивність джерела) не перевищує деякої величини (пропускної спроможності каналу), то при відповідному кодуванні і декодуванні можна звести ймовірність помилок в каналі до нуля.
Незабаром стало ясно, що фактичні обмеження на швидкість передачі встановлюються не пропускною спроможністю каналу, а складністю схем кодування і декодування. Тому зусилля розробників і дослідників в останні десятиліття були направлені на пошуки ефективних кодів, створення схем кодування і декодування, що практично реалізуються і по своїх характеристиках наближалися б до передбачених теоретично.
Розділ 1.Основи завадостійкого кодування
1.1 Основні принципи. Типи кодів
Кодування з виправленням помилок є методом обробки повідомлень, призначеним для підвищення надійності передачі по цифрових каналах. Хоча різні схеми кодування дуже несхожі один на одного і засновані на різних математичних теоріях, всім їм властиві дві загальні властивості.
Перше ? використання надмірності. Закодовані послідовності завжди містять додаткові, або надлишкові, символи. Кількість символів в кодовій послідовності Y завжди більша, ніж необхідно для однозначного представлення будь-якого повідомлення лi з алфавіту.
Друге -- властивість усереднення, що означає, що надлишкові символи залежать від декількох інформаційних символів, тобто інформація, що міститься в кодовій послідовності X, перерозподіляється також і на надлишкові символи.
Існує два великі класи коректуючи кодів ? блочні і згортальні. Визначальна відмінність між цими кодами полягає у відсутності або наявності пам'яті кодера.
Кодер для блочних кодів ділить безперервну інформаційну послідовність X на блоки-повідомлення довжиною k символів.
Кодер каналу перетворить блоки-повідомлення X в довші двійкові послідовності Y, що складаються з n символів і звані кодовими словами. Символи (n-к), що додаються до кожного блоку-повідомлення кодером, називаються надлишковими. Вони не несуть жодної додаткової інформації, і їх функція полягає в забезпеченні можливості виявляти (або виправляти) помилки, що виникають в процесі передачі.
Термін "без пам'яті" означає, що кожен блок з n символів залежить лише від відповідного інформаційного блоку з k символів і не залежить від інших блоків.
Кодер для згортальних кодів працює з інформаційною послідовністю без розбиття її на незалежні блоки. У кожен момент часу кодер з невеликого поточного блоку інформаційних символів розміром в b символів (блоку-повідомлення) утворює блок, що складається з v кодових символів (кодовий блок), причому v > b. При цьому кодовий v-символьний блок залежить не лише від b-символьного блока-повідомлення, присутнього на вході кодера зараз, але і від попередніх m блоків-повідомлень. У цьому, власне, і полягає наявність пам'яті в кодері. Блочне кодування зручно використовувати в тих випадках, коли вихідні дані за своєю природою вже згруповані в які-небудь блоки або масиви. При передачі по радіоканалах частіше використовується згортальне кодування, яке краще пристосоване до побітової передачі даних. Окрім цього, при однаковій надмірності згортальні коди, як правило, володіють кращою виправною здатністю.
1.2 Лінійні блочні коди
Для блочного коду з 2k кодовими словами завдовжки в n символів, якщо він лише не володіє спеціальною структурою, апарат кодування і декодування є дуже складним. Тому обмежимо свій розгляд лише кодами, які можуть бути реалізовані на практиці. Однією з умов реалізованості блочних кодів при великих k є умова їх лінійності. Що таке лінійний код?
Блочний код довжиною n символів, що складається з 2k кодових слів, називається лінійним (n, k) - кодом за умови, що все його 2k кодових слів утворюють k-мірний підпростір векторного простору n-послідовностей двійкового поля GF(2). Якщо сказати простіше, то двійковий код є лінійним, якщо додавання по модулю 2 ( mod2 ) двох кодових слів також є кодовим словом цього коду. Працюючи з двійковими кодами, ми постійно стикатимемося з елементами двійкової арифметики, тому визначимо основні поняття. Полем називається безліч математичних об'єктів, які можна додавати, віднімати, множити і ділити. Візьмемо просте поле, що складається з двох елементів ? нуля - 0 і одиниці - 1. Визначимо для нього операції додавання і множення:
0+0=0, 0 0=0; 0+1=1, 0 1=0; 1+0=1, 1 0=0; 1+1=0, 1 1=1.
Визначені таким чином операції додавання і множення називаються додаванням по модулю 2 ( mod2 ) і множенням по модулю 2.
Відзначимо, що з рівності 1+1 = 0 випливає, що -1 = 1 і, відповідно, 1+1=1-1, а з рівності 11=1 ? що 1:1=1.
Алфавіт з двох символів 0 і 1 разом із додаванням і множенням по mod2 називається полем з двох елементів і позначається як GF(2). До поля GF(2) застосовні всі методи лінійної алгебри, у тому числі матричні операції.
Ще раз звернемо увагу на те, що всі дії над символами в двійкових кодах виконуються по модулю 2.
Бажаною якістю лінійних блочних кодів є систематичність.
Систематичний код має формат, зображений на мал. 1.1, тобто містить незмінну інформаційну частину завдовжки k символів і надлишкову (перевірочну) довжиною n - k символів.
Размещено на http://www.allbest.ru/
35
1
Рис. 1.1
Блочний код, що володіє властивостями лінійності і систематичності, називається лінійним блочним систематичним (n, k) -кодом. Найпростішим лінійним блочним кодом є (n, n-1)- код, побудований за допомогою однієї загальної перевірки на парність. Наприклад, кодове слово (4,3)- коду можна записати у вигляді вектора-стовпця:
= ( m0, m1, m2, m0+m1+m2 ), (1.1)
де mi - символи інформаційної послідовності, що набувають значень 0 і 1, а додавання проводиться по модулю 2 ( mod2 ).
Пояснимо основну ідею перевірки на парність.
Нехай інформаційна послідовність джерела має вигляд
m = ( 1 0 1 ). (1.2)
Тоді відповідна їй кодова послідовність виглядатиме таким чином :
U = ( U0, U1, U2, U3 ) = ( 1 0 1 0 ),(1.3)
де перевірочний символ U3 формується шляхом додавання по mod2 символів інформаційної послідовності m :
U3 = m0 + m1 + m2 . (1.4)
Неважко відмітити, що якщо число одиниць в послідовності m парне, то результатом додавання буде 0, якщо непарне ? 1, тобто перевірочний символ доповнює кодову послідовність так, щоб кількість одиниць в ній була парною. При передачі по каналах зв'язку в прийнятій послідовності можлива поява помилок, тобто символи прийнятої послідовності можуть відрізнятися від відповідних символів переданої кодової послідовності (нуль переходить в одиницю, а 1 ? у 0). Якщо помилки в символах мають однакову ймовірність і незалежні, то ймовірність того, що в n-позиційному коді станеться лише одна помилка, буде
P1 = n Pпом (1- Pпом)n-1 (1.5)
(тобто в одному біті помилка є, а у всіх останніх n - 1 бітах помилки немає).
Ймовірність того, що станеться дві помилки, визначається вже числом можливих поєднань помилок по дві (у двох довільних бітах помилка є, а у всіх останніх n - 2 бітах помилки немає):
P2 = Cn2 Pпом (1- Pпом)n-2 , (1.6)
і аналогічно для помилок вищої кратності.
Якщо вважати, що ймовірність помилки на символ прийнятої послідовності Pпом достатньо мала (Pпом <<1), а інакше передача інформації не має сенсу, то ймовірність випадання рівно l помилок складе Pl Pпом l.
Звідси видно, що найбільш ймовірними є одиночні помилки, менш ймовірними -- подвійні, ще меншу ймовірність матимуть трикратні помилки і так далі.
Якщо при передачі даного (4,3) - коду сталася одна помилка, причому не важливо, в якій його позиції, то загальне число одиниць в прийнятій послідовності r вже не буде парним.
Таким чином, ознакою відсутності помилки в прийнятій послідовності може служити парність числа одиниць. Тому такі коди і називаються кодами з перевіркою на парність.
Правда, якщо в прийнятій послідовності r сталися дві помилки, то загальне число одиниць в ній знову стане парним і помилка виявлена не буде. Проте ймовірність подвійної помилки значно менша ймовірності одиночної, тому найбільш ймовірні одиночні помилки таким кодом виявлятися все ж будуть. Не дивлячись на свою простоту і не дуже високу ефективність, коди з перевіркою на парність широко використовуються в системах передачі і зберігання інформації. Вони цінуються за невисоку надмірність: досить додати до послідовності, що передається всього один надлишковий символ ? і можна взнати, чи є в прийнятій послідовності помилка. Правда, визначити місце цієї помилки і виправити її, поки не можна. Можна лише повторити передачу слова, в якому була допущена помилка, і тим самим її виправити.
Розділ 2. Поліноміальні коди
2.1 Основи поліноміальних кодів
Представлення кодового слова (n, k)-коду у вигляді послідовності U = (U0, U1, ..., Un-1 ) довжиною n символів або їх завдання за допомогою системи перевірочних рівнянь і породжує матриці не є єдино можливим. Ще один зручний і широко використовуваний спосіб представлення того ж кодового слова полягає в тому, що елементи U0, U1, ..., Un-1 є коефіцієнтами многочлена від X, тобто
U(х) = f(х) = U0 +U1* Х + U2*Х2 +...+Un- 1*Хn-1 . (1.51)
Використовуючи це подання, можна визначити поліноміальний код як безліч всіх многочленів ступеня, не більшої n -1, містять в якості загального множника деякий фіксований многочлен g(x).
Многочлен g(x) називається породжується многочленом коду. Представлення кодових слів у такій формі дозволяє звести дії над комбінаціями символів до дії над поліномами. Визначимо дії над поліномами в полі двійкових символів GF(2).Сумою двох поліномів f(x) і g(x) з GF(2)називається поліном з GF (2), який визначається наступним чином:
f(x)* g(x)= (1.52)
Іншими словами, додаванню двійкових поліномів відповідає додавання по mod2 коефіцієнтів при однакових степенях х.
Наприклад:
Твором двох поліномів з GF (2) називається поліном з GF (2), який визначається наступним чином:
f(x)* g(x)=
тобто твір виходить за звичайним правилом перемножування статичних функцій, проте одержувані коефіцієнти при даному степенні Х складаються по модулю 2.
Наприклад:
Нарешті, можна сформулювати теорему про поділ поліномів: для кожної пари поліномів С(х) и d(x), d(x) 0 0 існує єдина пара поліномів q(x) -- частка і p(х) -- залишок, такі, що
С(х) = q(x)* d(x) + p(х) , (1.58)
де степінь залишку p(х) менше степеня дільника d(x).
Іншими словами, поділ поліномів проводиться за правилами ділення статичних функцій, при цьому операція віднімання замінюється підсумовуванням за mod2.
Наприклад:
Ще раз нагадаємо, що при додаванні по mod2 сума двох одиниць (тобто двох елементів полінома з однаковими степенями) дорівнюватиме нулю, а не звичним у десятковій системі числення двом. І, крім цього, операції вирахування і складання по mod2 збігаються.
2.2 Кодування з використанням циклічних кодів
Припустимо, треба закодувати деяку інформаційну послідовність
m = (m0, m1, m2 ... mk-1), (1.62)
Відповідний їй поліном виглядає наступним чином:
m (x) = m0 + m1 * x + m2 * x2 + ... + mk-1 * xk-1. (1.63)
Помноживши m (x) на xn-k:
xn-k * m (x) = m0 * xn-k + m1 * xn-k +1 + ... + mk-1 * xn-1, (1.64)
отримаємо поліном степеня n-1 або меншою.
Скориставшись теоремою про поділ поліномів, можна записати
xn-k * m (x) = q (x) * g (x) + p (x), (1.65)
де q (x) і p (x) -частка і залишок від ділення полінома xn-k * m (x)
а породжує поліном g (x).
Оскільки степінь g (x) дорівнює (n-k), то степінь p (x) повинна бути (nk-1) або менше, а сам поліном p (x) буде мати вигляд
p (x) = p 0 + p 1 * x + p 2 * x2 + ... + p n-k-1 * xn-k-1, (1.66)
З урахуванням правил арифметики в GF (2) даний вираз можна переписати таким чином:
p (x) + xn-k * m (x) = q (x) * g (x), (1.67)
звідки видно, що поліном p (x) + xn-k * m (x) є кратним g (x) і має степінь n-1 або меншу. Отже, поліном p (x) + xn-k * m (x) - це кодовий поліном, відповідний до кодованої інформаційної послідовності m (x).
|
U = |
( 0, 1 ... n- k-1 , |
m0, m1 ... mk-1), |
|
|
Перевірочні символи |
Інформаційні символи |
Розкривши останній вираз, отримаємо
p (x) + m (x) * xn-k = p 0 + p 1 x + p 2 x2 .. + p n-k-1 xn-k-1 + m0 xn-k + m1 * xn-k + 1 + .. + mk-1 xn-1,
що відповідає кодовому слову
U = (p 0, p 1 ... p n-k-1, m0, m1 ... mk-1),
перевірочні символи інформаційні символи
Таким чином, кодове слово складається з незмінною інформаційної частини m, перед якою розташовано (n-k) перевірочних символів. Перевірочні символи є коефіцієнтами полінома p (x), тобто залишку від ділення m (x) * xn-k на породжує поліном g (x).
Щоб отриманий результат був зрозуміліше, нагадаємо, що множенню деякого двійкового полінома на xn-k відповідає зсув двійковій послідовності m = (m0, m1 ... mk-1) на n-k розрядів вправо.
Розглянемо приклад. З використанням коду, що задається породжує поліномом g (x) = 1 + x + x3, закодуємо довільну послідовність, наприклад m = (0111).
Послідовності m = (0111) відповідає поліном m (x) = x + x2 + x3.
Помножимо m (x) на xn-k:
m (x) * xn-k = m (x) * x3 = (x + x2 + x3) * x3 = x4 + x5 + x6, (1.68)
Розділимо m (x) * xn-k на породжує поліном g (x):
Таким чином, кодовий поліном, відповідний інформаційної послідовності m = (0111), буде мати наступний вигляд:
U(x) = 0X0 + 0X1 + 1X2 + 0X3 + 1X4 + 1X5 + 1X6, (1.70)
а відповідне кодове слово U = (0010111).
Отже, циклічний (n, k)-код k-розрядної інформаційної послідовності m = (m0, m1 ... mk-1) отримують таким чином:
- Інформаційну послідовність m множать на xn-k, тобто зрушують вправо на n-k розрядів;
- Поліном отриманої послідовності ділять на породжує поліном коду g (x);
- Отриманий залишок від ділення m (x) * xn-k на g (x) додають до m (x) * xn-k, тобто записують у молодших n-k розрядах коду.
Алгоритм кодування, заснований на розподілі поліномів, можна реалізувати, використовуючи схему поділу. Вона являє собою регістр зсуву, в якому ланцюга зворотного зв'язку замкнуті відповідно c коефіцієнтами породжує полінома g (x)
Рис. 1.10.
Кодування в схемі рис. 1.10 виконується таким чином:
- к символів інформаційної послідовності m через перемикач П, що знаходиться у верхньому положенні, один за іншим передаються в канал і одночасно з цим через відкриту схему И записуються в регістр перевірочних символів, в якому завдяки наявності ланцюгів зворотного зв'язку g0 ... gn-k-1 формується залишок від ділення xn-k * m (x) на g (x) - перевірочні символи;
- Починаючи з (k +1)-го такту перемикач переводиться в нижнє положення, і з зсувного регістру виводяться (n-k) перевірочних символів; ланцюг зворотного зв'язку при цьому розімкнута (схема И - закрита).
Для циклічного (7,4)-коду Хеммінга (а цей код має властивість циклічності), використовуваного в якості прикладу і має породжує поліном g (x) = 1 + x + x3, схема кодування виглядає наступним чином (рис. 1.11):
Рис. 1.11
У цій схемі, на відміну від узагальненої схеми кодера рис. 1.10, відсутні елементи в ланцюгах, де значення коефіцієнтів зворотного зв'язку gi дорівнюють нулю, там же, де коефіцієнти передачі gi рівні одиниці, ланцюг просто замкнута. На прикладі цього ж коду і відповідного йому кодера розглянемо в динаміці процес кодування довільної послідовності m.
Нехай m = (1001). Тоді послідовність станів осередків зсувного регістру із зворотними зв'язками в процесі кодування буде визначатися табл. 1.4.
Таблица 1.4
Ще однією важливою властивістю циклічного (n, k)-коду, що випливають з теореми про існування циклічних кодів, є те, що його породжує поліном ділить без залишку двочлен xn +1, тобто
xn + 1 = g (x) * h (x) + 0. (1.71)
Поліном h (x) - частка від ділення xn +1 на g (x) - називається перевірочним поліномом.
Оскільки h (x) однозначно пов'язаний з g (x) , він також визначає код. Отже, за допомогою перевірочного полінома h (x) теж можна виробляти кодування. Схема кодування на підставі перевірочного полінома h (x) наведена на рис. 1.12.
Рис. 1.12
Процедура кодування на підставі h (x) виглядає наступним чином:
1. На вході "Дозвіл" встановлюється 1, при цьому відкривається нижня схема И і закривається верхня.
2. Повідомлення m послідовно записується в k-розрядний зсувний регістр і одночасно з цим передається в канал.
3. Після закінчення введення k інформаційних символів на вході "Дозвіл" встановлюється 0, замикаючи через верхню схему И ланцюг зворотного зв'язку.
4. Виробляється (n-k) зрушень, при цьому формуються і видаються в канал (n-k) перевірочних символів.
Для циклічного (7,4)-коду до породжує поліномом g (x) = 1 + x + x3 перевірочний поліном h (x) має вигляд
(1.72)
З урахуванням цього схема кодування на підставі полінома h (x) для (7,4)-коду виглядає наступним чином (рис. 1.13):
Рис. 1.13
2.3 Обчислення синдрому і виправлення помилок в циклічних кодах
Обчислення синдрому для циклічних кодів є досить простою процедурою. Нехай U (x) і r (х) поліноми, відповідні переданому кодовому слову і прийнятої послідовності. Розділивши r (x) на g (x), отримаємо
r(x) = q(x)* g(x) + s(x), (1.73)
де - q (x) - частка від ділення, s (x) - залишок від ділення.
Якщо r (x) є кодовою поліномом, то він ділиться на g (x) без залишку, тобто s (x) = 0. Отже, s(x) 0 є умовою наявності помилки в прийнятій послідовності, тобто синдромом прийнятої послідовності.
Синдром s (x) має в загальному випадку вид
S(x) = S0 + S1 * x + ... + Sn- k-1 * xn-k-1 . (1.74)
Очевидно, що схема обчислення синдрому є схемою поділу, подібної схемами кодування рис. 1.10 або 1.11.
За наявності у прийнятій послідовності r хоча б однієї помилки вектор синдрому S буде мати, принаймні, один нульовий елемент, при цьому факт наявності помилки легко виявити, об'єднавши по IF виходи всіх осередків регістра синдрому. Покажемо, що синдромний многочлен S (x) однозначно пов'язаний з многочленом помилки e (x), а значить, з його допомогою можна не тільки виявляти, а й локалізувати помилку у прийнятій послідовності.
Нехай
e(x) = e0 + e1 * x + e2 * x2 + ... + en-1 * x n-1 ,(1.75)
- Поліном вектора помилки.
Тоді поліном прийнятої послідовності
r (x) = U (x) + e (x), (1.76)
Додамо в цьому виразі ліворуч і праворуч U (x), а також врахуємо, що
r(x) = q(x)* g(x) + S(x), U(x) = m(x)* g(x), (1.77)
тоді
(1.78)
тобто синдромний поліном S (x) є залишок від ділення полінома помилки e (x) на породжує поліном g (x).
Звідси випливає, що по синдрому S (x) можна однозначно визначити вектор помилки e (x), а отже, виправити цю помилку.
На рис. 1 наведена схема синдромного декодера з виправленням одноразової помилки для циклічного (7,4)-коду. За своєю структурою вона подібна схемі, наведеній на рис. 1.6, з тією лише різницею, що обчислення синдрому прийнятої послідовності виробляється тут не множенням на перевірочну матрицю, а поділом на породжує поліном. При цьому вона зберігає і недолік, властивий всім синдромних декодерів: необхідність мати запам'ятовуючий пристрій, що ставить у відповідність безлічі можливих синдромів S безліч векторів помилок e. Циклічність структури коду в цьому випадку не враховується.
Рис 1.14
Розділ 3. Практична частина
3.1 Інструкція користувача
Засобами програмного середовища Borland C++ Builder 6 розроблено программу для виявлення і виправлення помилок в циклічних кодах.
Для запуску програми потрібно запустити файл Polynom.exe
Після запуску програми відкриється вікно куди буде потрібно ввести дані
В текстове поле Cod потрібно ввести двійкове або деяткове число в якому програма повинна виправити помилку і вивести закодоване повідомлення
Для запуску програми потрібно натиснути кнопку:
Програма проведе обчислення за алгоритмом і виведе результат у вигляді двійкового коду:
3.2 Опис алгоритмів
Знаходження контрольного розряду за допогою табл 3.2.1. Визначення незвідного полінома(породжуючого многочлена) з табл 3.2.2
int r(int n)
{
if (n==3)return 2;
if (n==5)return 3;
if (n==6)return 3;
if (n==7)return 3;
if (n>=9&&n<=15)return 4;
if (n>=17&&n<=31)return 5;
if (n>=33&&n<=63)return 6;
if (n>=65&&n<=127)return 7;
else return 0;
};
Табл 3.2.1
|
n |
3 |
5 |
6 |
7 |
9...15 |
17...31 |
33...63 |
65...127 |
|
|
k |
1 |
2 |
3 |
4 |
5...11 |
12...26 |
27...57 |
28...120 |
|
|
r |
2 |
3 |
3 |
3 |
4 |
5 |
6 |
7 |
Табл 3.2.2
|
g(x) |
поліном |
g(x) |
поліном |
|
|
g(x) |
x+1 |
g1(x6) |
x6+x+1 |
|
|
g(x2) |
x2+x+1 |
g2(x6) |
x6+x3+1 |
|
|
g1(x3) |
x3+x1+1 |
g3(x6) |
x6+x5+1 |
|
|
g2(x3) |
x3+x2+1 |
…………… |
…………… |
|
|
g1(x4) |
x4+x+1 |
g1(x7) |
x7+x+1 |
|
|
g2(x4) |
x4+x3+1 |
g2(x7) |
x7+x3+1 |
|
|
g3(x4) |
x4+x3+x2+x+1 |
g3(x7) |
x7+x3+x2+x+1 |
|
|
g1(x5) |
x5+x2+1 |
…………… |
…………… |
|
|
g2(x5) |
x5+x3+1 |
g1(x8) |
x8+x4+x3+x+1 |
|
|
g3(x5) |
x5+x3+x4+x+1 |
g2(x8) |
x8+x4+x3+x2+1 |
|
|
g4(x5) |
x5+x4+x2+x+1 |
…………… |
…………… |
|
|
g5(x5) |
x5+x4+x3+x+1 |
g1(x9) |
x9+ x+1 |
|
|
g6(x5) |
x5+x4+x3+x2+1 |
g2(x9) |
x9+x4+ 1 |
Перевід з десяткової системи в двійкову:
int convertDecimalToBinary(int dec)
{
int bin = 0, pos = 1;
while(dec > 0)
{
bin = bin + (dec % 2) * pos;
dec = dec / 2;
pos *= 10;
}
return bin;
};
Функція підрахунку ваги залишку:
int vaga(AnsiString w) {
int count=0;
for(int i=1;i<=w.Length();i++) if (w[i]=='1') count++;
return count;
}
Функція видаляє з 1 позиції і-елементів:
AnsiString cutBinary(AnsiString s,int i)
{
return s.Delete(1,i);
}
Функція додавання по mod2 аналогічна операції xor:
AnsiString substringBinary(AnsiString s,int i)
{
return s.Delete(i+1,s.Length()-i-1);
}
AnsiString substractBinary(AnsiString s1,AnsiString s2)
{
AnsiString result="";
if(s1.Length()!=s2.Length()) return "error";
int n=s1.Length();
for(int i=1;i<=n;i++)
if(s1[i]==s2[i]) result+="0";
else result+="1";
int i=1;
while(result[i]=='0') i++;
i--;
result=cutBinary(result,i);
return result;
};
Функція ділить прийняту комбінацію на породжуючий многочлен, поки залишок не стане меншим за породжуючий многочлен і повертає залишок. Якщо під час зсувів утворюються 0 на початку у вхідній комбінації функція їх видаляє
AnsiString divBinary(AnsiString s1,AnsiString s2)
{
int j=1;
while (s1[j]=='0') j++;
s1.Delete(1,j-1);
AnsiString sB1=s1; AnsiString sZ=s1; AnsiString sR1=s1; int iter=1; int zal=s2.Length();
if(sB1.Length()>=s2.Length()) {
sB1.Delete(s2.Length()+1,zal);
sB1=substractBinary(sB1,s2);
int kol=s2.Length()-sB1.Length();
if(sB1.Length()+kol<zal){
return sB1;}
sR1.Delete(1,s2.Length());
if (sR1.Length()>=kol)
{
sB1+=sR1.SubString(1,kol);
zal+=sR1.SubString(1,kol).Length();
}
else
{
sB1+=sR1;
zal+=sR1.Length();
}
}
while(sB1.Length()>=s2.Length()) {
sR1=s1;
sR1.Delete(1,zal);
sB1=substractBinary(sB1,s2);
int kol=s2.Length()-sB1.Length();
if (sR1.Length()>=kol)
{
sB1+=sR1.SubString(1,kol);
zal+=sR1.SubString(1,kol).Length();
}
else
{
sB1+=sR1;
zal+=sR1.Length();
}
}
return sB1;
}
Цикл проводить циклічний зсув вліво поки вага залишку не стане меншою або рівною числу помилок яке в даному випадку завжди рівне 1.
while(z>s) {
cod=cod.SubString(2,cod.Length())+cod[1];
w=divBinary(cod,G[R]);
ShowMessage("w2:"+divBinary(cod,G[R]));
z=vaga(w);
s=1;
q++;
}
Якщо вага залишку менша або рівна 1 тоді ми додаємо її по mod2 до останьої комбінації яку ми ділим на породжуючий многочлен s проводимо циклічний зсув вправо q разів
if(z<=s) {
if (cod[cod.Length()]=='1')
cod[cod.Length()]='0';
else
if (cod[cod.Length()]=='0')
cod[cod.Length()]='1';
ShowMessage("code:"+cod);
int i=1;
while(i<=q)
{
cod=cod.SubString(cod.Length(),1)+cod.SubString(1,cod.Length()-1);
i++;
}
Висновки
кодування програма алгоритм
В даній курсовій роботі реалізовано завадостійке кодування процесом виявлення і виправлення одиничної помилки в циклічних кодах.
Створена програма може використовуватися при вивченні курсу «Теорія інформації та кодування».
Список використаної літератури
1. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. - К.: Видавнича група BHV. - 2007. - 368 с.:іл.
2. Вернер М. Основы кодирования. Учебник для ВУЗов. - М.: Техносфера. - 2004. - 288с.
3. В.И. Шульгин. Основы теории передачи информации. Ч. I. Экономное кодирование. - Учеб. пособие. - Харьков: Нац. аэрокосм. ун-т « Харьк. авиац. ин-т » , 2003. - 102 с.
4. В.И. Шульгин. Основы теории передачи информации.Ч.2. Помехоустойчивое кодирование. - Учеб. пособие. - Харьков: Нац. аэрокосм. ун-т « Харьк. авиац. ин-т » , 2003. - 87с.
5. Лидовский В.В. Теория информации. Учебное пособие.- М.: Компания Спутник+, -2004. -111с.
Додаток
#pragma hdrstop
#include<math.h>
#include<conio.h>
#include<string.h>
#include<iostream.h>
#include <vcl.h>
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
int r(int n)
{
if (n==3)return 2;
if (n==5)return 3;
if (n==6)return 3;
if (n==7)return 3;
if (n>=9&&n<=15)return 4;
if (n>=17&&n<=31)return 5;
if (n>=33&&n<=63)return 6;
if (n>=65&&n<=127)return 7;
else return 0;
};
int convertDecimalToBinary(int dec)
{
int bin = 0, pos = 1;
while(dec > 0)
{
bin = bin + (dec % 2) * pos;
dec = dec / 2;
pos *= 10;
}
return bin;
};
AnsiString cutBinary(AnsiString s,int i)
{
return s.Delete(1,i);
}
AnsiString substringBinary(AnsiString s,int i)
{
return s.Delete(i+1,s.Length()-i-1);
}
AnsiString substractBinary(AnsiString s1,AnsiString s2)
{
AnsiString result="";
if(s1.Length()!=s2.Length()) return "error";
int n=s1.Length();
for(int i=1;i<=n;i++)
if(s1[i]==s2[i]) result+="0";
else result+="1";
int i=1;
while(result[i]=='0') i++;
i--;
result=cutBinary(result,i);
return result;
};
AnsiString divBinary(AnsiString s1,AnsiString s2)
{
int j=1;
while (s1[j]=='0') j++;
s1.Delete(1,j-1);
AnsiString sB1=s1; AnsiString sZ=s1; AnsiString sR1=s1; int iter=1; int zal=s2.Length();
if(sB1.Length()>=s2.Length()) {
sB1.Delete(s2.Length()+1,zal);
sB1=substractBinary(sB1,s2);
int kol=s2.Length()-sB1.Length();
if(sB1.Length()+kol<zal){
return sB1;}
sR1.Delete(1,s2.Length());
if (sR1.Length()>=kol)
{
sB1+=sR1.SubString(1,kol);
zal+=sR1.SubString(1,kol).Length();
}
else
{
sB1+=sR1;
zal+=sR1.Length();
}
}
while(sB1.Length()>=s2.Length()) {
sR1=s1;
sR1.Delete(1,zal);
sB1=substractBinary(sB1,s2);
int kol=s2.Length()-sB1.Length();
if (sR1.Length()>=kol)
{
sB1+=sR1.SubString(1,kol);
zal+=sR1.SubString(1,kol).Length();
}
else
{
sB1+=sR1;
zal+=sR1.Length();
}
}
return sB1;
}
int vaga(AnsiString w) {
int count=0;
for(int i=1;i<=w.Length();i++) if (w[i]=='1') count++;
return count;
}
void __fastcall TForm1::Button1Click(TObject *Sender)
{
AnsiString w="";
AnsiString cod="";
if (cmb1->ItemIndex==0)
cod=Edit1->Text;
else if (cmb1->ItemIndex==1)
cod=IntToStr(convertDecimalToBinary(StrToInt(Edit1->Text)));
int n=cod.Length();
int R=r(n);
if (R==0) {return;}
Edit2->Text=R;
String G[10];
G[1]="11"; G[2]="111"; G[3]="1011"; G[4]="10011"; G[5]="100101"; G[6]="1000011";
G[7]="10000011"; G[8]="100011011"; G[9]="1000000011";
w=divBinary(cod,G[R]);
ShowMessage("w1:"+divBinary(cod,G[R]));
int z=vaga(w);
int s=1;
int q=0;
while(z>s) {
cod=cod.SubString(2,cod.Length())+cod[1];
w=divBinary(cod,G[R]);
ShowMessage("w2:"+divBinary(cod,G[R]));
z=vaga(w);
s=1;
q++;
}
if(z<=s) {
if (cod[cod.Length()]=='1')
cod[cod.Length()]='0';
else
if (cod[cod.Length()]=='0')
cod[cod.Length()]='1';
ShowMessage("code:"+cod);
int i=1;
while(i<=q)
{
cod=cod.SubString(cod.Length(),1)+cod.SubString(1,cod.Length()-1);
i++;
}
Form1->Edit3->Text=cod;
}
}
Размещено на Allbest.ru
Подобные документы
Розробка та дослідження алгоритмів і програм кодування даних з виявленням помилок на основі циклічних CRC-кодів. Аналіз циклічних кодів. Розробка та тестування програмних модулів. Розрахунок економічних показників. Вирішення питань охорони праці.
дипломная работа [5,4 M], добавлен 22.06.2010Імовірнисний підхід у теорії ощадливого кодування. Оцінка інформативності ознак та їх оптимальна градація. Застосування імовірнісних методів для підвищення ефективності ощадливого кодування відеоінформації. Ефективні алгоритми кодування інформації.
реферат [1,6 M], добавлен 29.06.2009Реалізація програми, яка буде забезпечувати шифрування і дешифрування будь-яких файлів по довільному алгоритму з використанням пароля. Можливість кодування та розкодування утиліти за простим алгоритмом Гамування, який базується на бітовій операції XOR.
лабораторная работа [15,1 K], добавлен 04.04.2011Історія створення мови С#. Аналіз алгоритмів кодування даних. Розробка системи в середовищі Visual Studio 2008 Express. Схема шифрування алгоритму DES. Дослідження алгоритму RC2. Приклади хешів RIPEMD-160. Програмна реалізація основних процедур системи.
дипломная работа [1,7 M], добавлен 25.10.2012Характеристики методів стискання інформації. Дворівневе кодування, алгоритм Лемпеля-Зіва. Блок-схема алгоритму кодування. Вибір мови, середовища програмування. Опис інтерфейсу, тестування програми. Бібліотеки, які використовуються при написанні програми.
курсовая работа [728,9 K], добавлен 17.01.2014Значимість двійкової системи числення для кодування інформації. Способи кодування і декодування інформації в комп'ютері. Відповідність десятковій, двійковій, вісімковій і шістнадцятковій систем числення. Двійкове кодування інформації, алфавіт цифр.
презентация [1,4 M], добавлен 30.09.2013Перевірка коду на парність. Формула для підрахунку парності або непарності одиниць в інформаційних розрядах. Побудова групових кодів і їх вживання для виявлення і виправлення помилок. Правила формування перевірочних символів. Використання кодів Хемминга.
лабораторная работа [639,7 K], добавлен 17.12.2010Принципи побудови та функціонування алгоритмів розпізнавання та виправлення помилок в кодових послідовностях. Переклад символів імені у послідовність цифр 16-річної системи числення. Заміна на протилежне значення біту і можливість його виправлення.
курсовая работа [660,0 K], добавлен 02.10.2010Сучасні методи захисту текстової інформації. Порівняльний аналіз шифру Бекона з іншими відомими шифрами. Практичне використання алгоритмів кодування тексту. Написання програми "Шифр Бекона", використані компоненти для реалізації алгоритму, їх властивості.
курсовая работа [606,8 K], добавлен 28.03.2016Практичне застосування систем кодування знакової та графічної інформації в електронних обчислювальних машинах. Позиційні системи числення. Представлення цілих і дійсних чисел. Машинні одиниці інформації. Основні системи кодування текстових даних.
практическая работа [489,5 K], добавлен 21.03.2012
