Білоруський державний університет інформатики і радіоелектроніки
Кафедра радіотехнічних систем
РЕФЕРАТ
На тему:
«Параметри кодів. Контроль, виявлення та виправлення помилок »
МІНСЬК, 2008
1. Параметри кодів
Визначення 1. Код - це безліч дискретних сигналів, обране для передачі повідомлень. Коди характеризуються такими параметрами:
1 Заснування коду - Число елементів множини , Обране для побудови коду. Наприклад, якщо:
а) , То для трійкового коду;
б) для двійкового коду.
Практично .
Зауваження - Ефективність каналів передачі (зберігання) інформації зростає з переходом на Недвійкова коди.
2 Довжина коду (Значности) - число символів кодового слова.
Визначення 2. Послідовності елементів (символів) довжиною називаються кодовими словами або кодовими векторами. Кажуть, що слово
має довжину ; ,
Параметр визначає наступні особливості класу кодів. Коди бувають:
а) рівномірні (блокові), ;
б) нерівномірні, ;
в) нескінченні, . До нескінченним відносять коди:
1) сверточних;
2) ланцюгові;
3) безперервні.
У рівномірних (блокових) кодів потік даних розділяється на блоки по інформаційних символів, і далі вони кодуються - Символьними кодовими словами.
Для безперервного коду потік даних розбивається на блоки довжини , Які називаються кадрами інформаційних символів. Ці кадри кодуються символами кодового слова (кадрами кодового слова). При цьому кодування кожного кадру інформаційних символів в окремі кадри кодового слова проводиться з урахуванням попередніх кадрів інформаційних символів.
блок блок блок блок
Безперервний код
Малюнок 1.1
3 Розмірність коду - Число інформаційних позицій кодового слова.
4 Потужність коду - Кількість різних кодових послідовностей (комбінацій), що використовуються для кодування.
- Максимальне число кодових комбінацій при заданих і . Наприклад, ; ; .
Визначення 3. Код, у якого використовуються всі комбінації, називається повним (безізбиточним).
Визначення 4. Якщо число кодових слів коду , То код називається надлишковим.
Приклад - Нехай , , .
Код - Надлишковий; .
5 Число перевірочних (надлишкових) позицій кодового слова .
Нехай , , . Тоді на довжині слова з семи символів - три надлишкових.
6 Швидкість передачі коду . Для наведеного прикладу .
7 Кратність помилки . Параметр вказує, що всі конфігурації з
або менше помилок в будь-якому кодовому слові можуть бути виправлені.
8 Відстань Хеммінга між двома векторами (ступінь віддаленості будь-яких кодових послідовностей один від одного) .
Визначення 5. Якщо і кодові вектори, то відстань Хеммінга дорівнює числу позицій, в яких вони розрізняються. Може позначатися і як - . Наприклад, ; .
Зауваження - З позиції теорії кодування показує, скільки символів у слові треба спотворити, щоб перевести одне кодове слово в інше.
9 Кодове відстань (мінімальна відстань коду) .
Визначення 6. Найменше значення відстані Хеммінга для всіх пар кодових послідовностей коду називають кодовою відстанню. , Де ; ; .
Визначення 7. Код значности , Розмірності і відстані називається - Кодом.
Приклад - Можна побудувати наступний код:
; ; ; .
Даний код можна використовувати для кодування 2-бітових двійкових чисел,
використовуючи наступне (довільна) відповідність:
Знайдемо кодова відстань цього коду:
;
;
;
;
;
.
Отже, для цього коду .
Зауваження - характеризує коригуючу здатність коду .
10 Вага Хеммінга вектора дорівнює числу ненульових позицій , Позначається . Наприклад, .
Використовуючи визначення ваги Хеммінга, отримаємо очевидне вираз (1.1)
Приклад - ;
.
З виразу (1.1) випливає, що мінімальна відстань Хеммінга одно , Де ; ; .
Зауваження - Для знаходження мінімального відстані лінійного коду не обов'язково порівнювати всі можливі пари кодових слів. Якщо
Теорема 1. Мінімальна відстань лінійного коду одно мінімальній вазі ненульових кодових слів.
Оскільки , То виникає питання про величину , Такий, щоб код забезпечував контроль помилок, тобто виявлення та виправлення помилок.
2 Контроль помилок
Кодове слово можна представити у вигляді вектора з координатами в - Мірному векторному просторі. Наприклад, для вектор знаходиться в тривимірному евклідовому просторі, малюнок 1.2. Дозволеними для передачі обрані вектора і .
X 0
1 0 0 1 1 0
1 0 1 1 1 1
0 0 0 0 1 0 X 1
0 0 1 0 1 1
X 2
а) кодові слова повного коду визначають - Мірний простір, що складається з послідовностей ( - Тривимірний простір, що складається при з 8 послідовностей повного коду);
б) кодові слова надлишкового коду визначають підпростір (підмножина) - Мірного простору, що складається з послідовностей.
Під впливом перешкод відбувається спотворення окремих розрядів слова. У результаті дозволені для передачі кодові вектори переходять в інші вектори (з іншими координатами) - заборонені. Факт переходу дозволеного слова у заборонений для передачі слово можна використовувати для контролю за помилками.
Можлива ситуація, коли дозволений вектор переходить в інший дозволений кодовий вектор: . У цьому випадку помилки не виявляються, і контроль стає неефективним.
З розглянутої моделі можна зробити наступний важливий висновок: для
того щоб передаються вектори можна було б відрізняти один від одного при наявності перешкод, необхідно розташовувати ці вектори в - Мірному просторі
якнайдалі один від одного. З цієї ж - Мірної моделі слід геометрична інтерпретація відстані Хеммінга: - Це число ребер, які потрібно пройти, щоб перекласти один вектор в іншій, тобто потрапити з вершини одного вектора в вершину іншого.
2.1 Виявлення і виправлення помилок
Стратегія виявлення полягає в наступному. Декодер виявляє помилку при апріорному умови, що переданим словом було найближчим по відстані до прийнятого слову. Покажемо застосування цього твердження.
Приклад 1. Нехай ; . Дозволеним для передачі є безліч кодових слів:
.
Очевидно, що код має . Будь-яка одиночна помилка трансформує дане кодове слово в інше дозволене слово. Це випадок безізбиточного коду, який не володіє корегуючої можливістю.
Приклад 2. Нехай тепер підмножина дозволених кодових слів надано у вигляді двійкових комбінацій з парним числом одиниць.
.
Поставлене код має . Заборонені кодові слова представлені у вигляді підмножини :
.
Якщо , То жодне з дозволених кодових слів (тобто коду ) При одиночній помилку не переходить в інше дозволене слово цього ж коду. Таким чином, код виявляє:
- Поодинокі помилки;
- Помилки непарної кратності (для - Потрійні).
Наприклад, потрійна помилка кодового слова ; , Переводить його в заборонений вектор .
Висновок - У загальному випадку, при необхідності виявляти помилки кратності кодова відстань коду повинна бути
.
Приклад 3. Нехай ; ; Код заданий векторами і .
При виникненні одиночних помилок або безлічі векторів
кодовому слову відповідає наступне заборонене підмножина
.
Кодовому слову відповідає заборонене підмножина
= =
Таким чином, коду - Дозволеному для передачі підмножин векторів відповідає два заборонених підмножини векторів і :
=
= .
=
Стратегія виправлення помилок полягає в наступному:
- Кожна з поодиноких помилок призводить до забороненого кодовому слову того чи іншого забороненого підмножини ( і );
- Структура кодового забороненого підмножини, що відноситься до відповідного вихідного дозволеному підмножині, дозволяє визначити місце розташування помилки, тобто виправити помилку.
Для виправлення помилок кратності кодова відстань має задовольняти співвідношенню . (1.2)
Використовуючи цю формулу, можна записати
,
де позначає цілу частину числа .
Зауваження - Існують моделі каналів (наприклад, канал з дефектами), в яких величина може бути більше, ніж у виразі (1.2).
ЛІТЕРАТУРА
· Митюхина А.І., Ігнатович В.Г. Лінійні групові коди: Учеб. посібник. - Мн. : БДУІР, 2002.
· Митюхина А.І. Елементи абстрактної алгебри: Учеб.пособие. - Мн.: БДУІР, 2000.
· Лосєв В.В. Завадостійке кодування в радіотехнічних системах передачі інформації: Метод. Посібник Ч.1. Лінійні коди. - Мн.: ВШ, 2004.
Кафедра радіотехнічних систем
РЕФЕРАТ
На тему:
«Параметри кодів. Контроль, виявлення та виправлення помилок »
МІНСЬК, 2008
1. Параметри кодів
Визначення 1. Код - це безліч дискретних сигналів, обране для передачі повідомлень. Коди характеризуються такими параметрами:
1 Заснування коду
а)
б)
Практично
Зауваження - Ефективність каналів передачі (зберігання) інформації зростає з переходом на Недвійкова коди.
2 Довжина коду
Визначення 2. Послідовності елементів (символів) довжиною
Параметр
а) рівномірні (блокові),
б) нерівномірні,
в) нескінченні,
1) сверточних;
2) ланцюгові;
3) безперервні.
У рівномірних (блокових) кодів потік даних розділяється на блоки по
Для безперервного коду потік даних розбивається на блоки довжини
На малюнку 1.1 показані структури кодування блоковими і безперервними кодами.
k-бітовий n-бітовий n-бітовий k-бітовий Кодер |
Канал |
Декодер |
Блоковий код
k 0 бітів / кадр n 0 бітів / кадр n 0 бітів / кадр k 0 бітів / кадрКодер |
Канал |
Декодер |
Безперервний код
Малюнок 1.1
3 Розмірність коду
4 Потужність коду
Визначення 3. Код, у якого використовуються всі комбінації, називається повним (безізбиточним).
Визначення 4. Якщо число кодових слів коду
Приклад - Нехай
Код
5 Число перевірочних (надлишкових) позицій кодового слова
Нехай
6 Швидкість передачі коду
7 Кратність помилки
або менше помилок в будь-якому кодовому слові можуть бути виправлені.
8 Відстань Хеммінга між двома векторами (ступінь віддаленості будь-яких кодових послідовностей один від одного)
Визначення 5. Якщо
Зауваження - З позиції теорії кодування
9 Кодове відстань (мінімальна відстань коду)
Визначення 6. Найменше значення відстані Хеммінга для всіх пар кодових послідовностей коду називають кодовою відстанню.
Визначення 7. Код значности
Приклад - Можна побудувати наступний код:
Даний код можна використовувати для кодування 2-бітових двійкових чисел,
використовуючи наступне (довільна) відповідність:
Знайдемо кодова відстань цього коду:
Отже, для цього коду
Зауваження -
10 Вага Хеммінга вектора
Використовуючи визначення ваги Хеммінга, отримаємо очевидне вираз
Приклад -
|
З виразу (1.1) випливає, що мінімальна відстань Хеммінга одно
Зауваження - Для знаходження мінімального відстані лінійного коду не обов'язково порівнювати всі можливі пари кодових слів. Якщо і належать лінійному коду , То - Також є кодовим словом коду . Такий код є адитивною групою (визначена операція додавання) і, отже, , Де і , Тобто справедлива теорема.
Теорема 1. Мінімальна відстань лінійного коду одно мінімальній вазі ненульових кодових слів. Оскільки
2 Контроль помилок
Кодове слово можна представити у вигляді вектора з координатами в
X 0
1 0 0 1 1 0
1 0 1 1 1 1
0 0 0 0 1 0 X 1
0 0 1 0 1 1
X 2
Малюнок 1.2
Малюнок дає наочну алгебраїчну інтерпретацію поняття "потужність коду":а) кодові слова повного коду визначають
б) кодові слова надлишкового коду визначають підпростір (підмножина)
Під впливом перешкод відбувається спотворення окремих розрядів слова. У результаті дозволені для передачі кодові вектори переходять в інші вектори (з іншими координатами) - заборонені. Факт переходу дозволеного слова у заборонений для передачі слово можна використовувати для контролю за помилками.
Можлива ситуація, коли дозволений вектор переходить в інший дозволений кодовий вектор:
З розглянутої моделі можна зробити наступний важливий висновок: для
того щоб передаються вектори можна було б відрізняти один від одного при наявності перешкод, необхідно розташовувати ці вектори в
якнайдалі один від одного. З цієї ж
2.1 Виявлення і виправлення помилок
Стратегія виявлення полягає в наступному. Декодер виявляє помилку при апріорному умови, що переданим словом було найближчим по відстані до прийнятого слову. Покажемо застосування цього твердження.
Приклад 1. Нехай
Очевидно, що код
Приклад 2. Нехай тепер підмножина
Поставлене код
Якщо
- Поодинокі помилки;
- Помилки непарної кратності (для
Наприклад, потрійна помилка кодового слова
Висновок - У загальному випадку, при необхідності виявляти помилки кратності
Приклад 3. Нехай
При виникненні одиночних помилок або безлічі векторів
кодовому слову
|
|
Таким чином, коду
Стратегія виправлення помилок полягає в наступному:
- Кожна з поодиноких помилок призводить до забороненого кодовому слову того чи іншого забороненого підмножини (
- Структура кодового забороненого підмножини, що відноситься до відповідного вихідного дозволеному підмножині, дозволяє визначити місце розташування помилки, тобто виправити помилку.
Для виправлення помилок кратності
Використовуючи цю формулу, можна записати
де
Зауваження - Існують моделі каналів (наприклад, канал з дефектами), в яких величина
ЛІТЕРАТУРА
· Митюхина А.І., Ігнатович В.Г. Лінійні групові коди: Учеб. посібник. - Мн. : БДУІР, 2002.
· Митюхина А.І. Елементи абстрактної алгебри: Учеб.пособие. - Мн.: БДУІР, 2000.
· Лосєв В.В. Завадостійке кодування в радіотехнічних системах передачі інформації: Метод. Посібник Ч.1. Лінійні коди. - Мн.: ВШ, 2004.