Алгоритм кодування Ріда-Малера
На початку будується виробляє матриця G , перший рядок якої містить n одиниць. Далі слід m рядків , сукупність яких зручно розглядати як ( m * n ) - матрицю , в якості стовпців якої обрані двійкові числа ( починаючи з нуля) . Номери розрядів двійкових чисел зручно вважати зверху вниз. Ці m рядків визначають вектори першого порядку . Далі йдуть рядки векторів другого порядку , які виходять з усіх творів двох рядків першого порядку , потім - рядки третього порядку , які є всіма творами трьох рядків першого порядку і т д.
Приклад: т=3 =2 п=2т=23=8
Для кодування визначається загальне число символів в блоці через інформаційні символи, підсумовуючи ненульові позиції відповідного стовпчика, що утворює матриці. Одиниці в шпальтах матриці G показують, які саме інформаційні символи Uk визначають значення символів Ui кодового слова.
Нехай стала послідовність:
Отримуємо: 11101011
Декодування здійснюється за мажоритарним принципом або принципом більшості. Декодування здійснюється спочатку для всіх інформаційних символів (окрім 1-го) на основі так званих парних компонентів. Починати запис таких рівнянь треба з векторів максимального порядку.
У нашому прикладі = 2 = першим виписується Uk5.
Для векторів 2-го порядку парними вважаються компоненти:
00 0
01 1
На другому рівні поєднань кожен 0 з'єднується з кожною 1 попарно. Тепер в проверяемое рівність виписуються всі об'єднані позиції 1-го і 2-го рівнів.
Вираховуємо символ Uk6
Для Uk7:
При декодуванні за допомогою векторів 1-го порядку ми також точно користуємося парними компонентами, але оскільки тут 1-ий рівень, то ми об'єднуємо просто 0 і 1, що стоїть на відповідних позиціях, і, по-друге, при декодуванні в отриманих рівняннях використовують не вихідне, а перетворене рівняння, яке виходить шляхом додавання за модулем два вихідного рівняння і векторів 2-го порядку, (тому що матриця має 2-ий порядок),
Після цього ще раз перетворять вихідне вираз: до отриманого преобразованному висловом додаємо вектори 1-го порядку, які містять одиницю у відповідному інформаційному розряді.
Якщо в отриманому виразі отримали всі 1, то значить U k1 = 1, а якщо все 0,_то_Uk1=0. Якщо при передачі відбулися спотворення, то обчислюваний символ по кожній системі перевірок вибирається за мажоритарним принципом, в тому числі і для символу U k1.
Висновок Список використаної літератури
Кудряшов Б.Д. Теорія інформації. Підручник для вузів Вид-во ПИТЕР, 2008. - 320с.
Єфімова О., Морозов В., Угринович Н. Курс комп'ютерної технології з основами інформатики. Навчальний посібник для старших класів. М., 2000. 4. Семенюк В.В. Економне кодування дискретної інформації. - СПб.: СПбГІТМО (ТУ), 2001 5. Дмитрієв В.І. Прикладна теорія інформації. М.: Вища школа, 1989. 6. Нефьодов В.М., Осипова В.А. Курс дискретної математики. М.: МАІ, 1992. 7. Колесник В.Д., Полтирев Г.Ш. Курс теорії інформації. М.: Наука, 2006.
2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. Москва: Мир, 1986 г.
3. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979 г.
4. Дмитриев В. И. Прикладная теория информации. М.: Высшая школа, 1989г.
5. Королёв А. И. Коды и устройства помехоустойчивого кодирования информации. Минск, 2010.
http://ua-referat.com