Білоруський державний університет інформатики і радіоелектроніки Кафедра радіотехнічних систем РЕФЕРАТ На тему: «Параметри кодів. Контроль, виявлення та виправлення помилок » МІНСЬК, 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.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.