Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Практичне до одірованія по Хеммінга»
МІНСЬК, 2009
Нехай нам належить закодувати текст, записаний на деякій мові, такому, що кількість літер в алфавіті цієї мови n = 2 m (m ціле число), а поява в тексті тих чи інших літер алфавіту равновероятно і не залежить від того, які букви їм передували . Тоді маємо
p (i) = p (j) = 1 / n; H = log 2 = m.
Умови задачі такі, що досягти оптимального кодування можна самим простим методом кодування - Політерний кодуванням з постійною довжиною (l = m) кодових наборів. При цьому, однак, ми опинилися б позбавлені будь-якої можливості виявляти, а тим більше виправляти помилки. Щоб така можливість з'явилася, необхідно відмовитися від оптимальності коду, "розщедритися" на кілька додаткових двійкових символів на букву, тобто навмисне ввести деяку надмірність, яка змогла б допомогти нам виявити або виправити помилки. Необхідна кількість додатково вводяться двійкових символів на одну букву позначимо через x, і тоді довжина кодового набору стане рівною l = m + x. Приймемо, що в результаті перешкод (випадкових чи навмисних) лише один або зовсім ніякий з m + x двійкових символів може перетворюватися з одиниці в нуль або, навпаки, з нуля в одиницю. Приймемо далі, що 1 + m + x подій, які полягають в тому, що помилка взагалі не відбудеться, відбудеться на рівні першого, другого, .... (M + x)-го символу кодового набору, рівноймовірні. Ентропію вгадування того, яке саме з цих 1 + m + x подій буде мати місце, в силу равновероятности цих подій можна визначити за формулою Н = log 2 (1 + m + х) біт. Таким чином, для виявлення самого факту наявності одиночної помилки і встановлення її позиції необхідно дістати інформацію в кількості не менше Н = log 2 (1 + m + x) біт. Джерелом цієї інформації слугують лише додатково введені x двійкових символів, тому що інші m символів з-за оптимальності кодування до межі зайняті описом самого тексту. Зауважимо, що x двійкових символів у кращому випадку можуть містити інформацію у кількості x біт. Таким чином, при конструюванні коду, що виявляє і виправляє одиночну помилку, слід врахувати, що цього можна домогтися лише при значеннях x, що задовольняють нерівності
х> = log 2 (l + m + x),
або 2 x-x-1> = m.
Рис. 1.Завісімость нижньої межі допустимих значень x від m (суцільна лінія) і залежність відносної надлишковості від m (пунктирна лінія).
Р. Хеммінга розробив конкретну конструкцію коду. яка забезпечує дуже елегантне виявлення та виправлення одиночних помилок при мінімально можливому числі додатково вводяться двійкових символів, тобто при знаку рівності. Простежимо за побудовою цього коду, коли m = 4. З малюнка випливає, що при цьому допустиме значення x дорівнює трьом, тобто при числі основних (інформаційних) двійкових символів m = 4, число додатково введених, тобто контрольних символів має бути не менше трьох. Приймемо, що нам вдалося "обійтися" саме трьома додатковими символами, тобто вдалося сконструювати такий код, за якого кожен з додатково введених трьох символів дає нам максимально можливу кількість інформації, тобто по одному біту. Тоді у розширеному кодовому наборі виявляться сім двійкових символів:
V e = AV a,
де V e, - вектор помилки, що вказує на її місце розташування; А - основна матриця, стовпці якої суть виконавчі запису чисел від одного до семи.
Операція додавання в усіх трьох рівняннях (14) - (16) здійснюється за модулем два. Підставляючи в систему рівнянні (14) - (16) e 0 = e 1 = e 2 = 0, отримаємо систему з трьох рівнянь
Рішення системи (17) - (19), або. що те ж саме, матричного рівняння (20) щодо B5, B6, B7 призводить до конкретних виразів для функцій (1) - (3):
Відзначивши, що при вказаній рекомендації Р. Хеммінга контрольна матриця завжди (незалежно від m і x) виявляється дорівнює одиниці, докладне обговорення цієї рекомендації залишимо на потім, продовжуючи розглядати в якості контрольних B5B6B7 а як інформаційних - B1B2B3B4.
Розглянемо, наприклад, набір інформаційних символів B1B2B3B4 = 1011. За допомогою залежностей (22) - (24) визначимо набір контрольних (додатково введених, надлишкових) символів B5B6B7 = 010. Нехай помилка сталася на рівні символу B5 тобто замість істинного розширеного кодового набору 1011 (0) 10 отримано код 1011 (1) 10. Тоді за допомогою залежностей (14) - (16) знайдемо
Наведена схема Р. Хеммінга з конструювання коду, що виявляє і виправляє одиночну помилку, універсальна, і аналогічний код може бути побудований для довільної пари значень m і x, що задовольняють рівнянню
А тепер повернемося до розгляду питання про те, чому Р. Хеммінга в якості контрольних бере саме символи, індекси яких рівні цілим ступенями двійки, тобто 1, 2, 4, 8, 16 ,.... По-перше, як уже йшлося раніше вище, при такому виборі контрольна матриця завжди виявляється дорівнює одиниці, тобто фактично знімається питання вирішення системи (22) - (24) щодо контрольних символів, так як її "рішення" зводиться до простого переписування відповідних рівнянь. Але це не головне, так як систему (22) - (24) доводиться вирішувати тільки один раз і далі при кожному акті кодування ми користуємося лише системою (11) - (13) - рішенням системи (22) - (24) щодо контрольних символів . При реалізації процедур кодування і декодування на ЕОМ сам факт, що контрольні символи роз'єднані (не йдуть підряд один за одним), створює певні незручності при кожному акті кодування і декодування. Природно тому бажання вибрати контрольні символи такими, щоб вони йшли поспіль один за одним, нехай навіть ціною того, щоб один раз вирішити систему (14) - (16). Саме так робили ми, коли всупереч рекомендації Р. Хеммінга взяти в якості контрольних символи B1, B2 і B4 взяли в їх якості символи B5, B6 і B7. Хоча це й змусило нас вирішити систему відносно змінних B5, B6 і B7, але зате при кожному акті кодування і декодування ми змогли оперувати "пачками" контрольних символів, а не "виколупувати" їх серед інформаційних символів.
Виникає питання, а чи завжди, при будь-якій кількості інформаційних символів ми змогли б надходити аналогічним чином? Ні, не змогли б, якщо як і раніше хочемо, щоб двійковий набір символів e x-1, e x-2 ,..., e 0 вказував на адресу помилки. Бо вже коли число контрольних символів більше трьох, ми не маємо права взяти в якості контрольних останні х символів. Легко переконатися, що при цьому контрольна матриця неодмінно була б виродженою, тобто значення її детермінанта виявилася б рівним нулю. Більш того, навіть у розглянутому нами випадку, коли число контрольних символів дорівнює трьом, ми не змогли б в якості контрольних взяти, наприклад, перші три символи. У всіх цих випадках визначники контрольних матриць (згадаємо, що стовпчики цієї матриці суть виконавчі запису номерів обраних нами контрольних символів) виявляються рівними нулю. Нехай, наприклад, ми вибрали в якості контрольних не пачку символів B5, B6, B7, а символи B1, B2, B3. Тоді нам довелося б мати справу з квадратною матрицею третього порядку, стовпці якої є двійковими формами запису чисел 1, 2 і 3:
Таким чином, при виборі серед m + x символів x контрольних слід дбати про те, щоб визначник контрольної матриці порядку x, стовпці якої є виконавчі запису номерів вибраних символів, не виявився рівним нулю. Саме щоб позбутися від цих турбот, Р. Хеммінга рекомендує в якості контрольних взяти символи з індексами I, 2, 4, 8 і т.д. Легко виявити, що при такому виборі контрольних символів ми завжди (незалежно від їх числа) будемо мати справу з одиничною матрицею.
Крім залежності (10). на малюнку приведена також залежність відносної надлишковості від m. Легко помітити, що зі збільшенням m потрібний процент надмірності для виявлення та виправлення одиночної помилки різко зменшується. Настільки неприродний результат є наслідком штучного, далекого від реальності допущення, що в рамках кожного кодового набору незалежно від його довжини m + x може відбутися не більше однієї помилки. Якщо ж припустити можливість двох і більше помилок, то завдання їх виявлення, і тим більше виправлення ускладнюється. Побудувати для цих випадків коди настільки ж елегантні, як код Р. Хеммннга для одиночної помилки, поки не вдалося.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.
кафедра РЕЗ
реферат на тему:
«Практичне до одірованія по Хеммінга»
МІНСЬК, 2009
Нехай нам належить закодувати текст, записаний на деякій мові, такому, що кількість літер в алфавіті цієї мови n = 2 m (m ціле число), а поява в тексті тих чи інших літер алфавіту равновероятно і не залежить від того, які букви їм передували . Тоді маємо
p (i) = p (j) = 1 / n; H = log 2 = m.
Умови задачі такі, що досягти оптимального кодування можна самим простим методом кодування - Політерний кодуванням з постійною довжиною (l = m) кодових наборів. При цьому, однак, ми опинилися б позбавлені будь-якої можливості виявляти, а тим більше виправляти помилки. Щоб така можливість з'явилася, необхідно відмовитися від оптимальності коду, "розщедритися" на кілька додаткових двійкових символів на букву, тобто навмисне ввести деяку надмірність, яка змогла б допомогти нам виявити або виправити помилки. Необхідна кількість додатково вводяться двійкових символів на одну букву позначимо через x, і тоді довжина кодового набору стане рівною l = m + x. Приймемо, що в результаті перешкод (випадкових чи навмисних) лише один або зовсім ніякий з m + x двійкових символів може перетворюватися з одиниці в нуль або, навпаки, з нуля в одиницю. Приймемо далі, що 1 + m + x подій, які полягають в тому, що помилка взагалі не відбудеться, відбудеться на рівні першого, другого, .... (M + x)-го символу кодового набору, рівноймовірні. Ентропію вгадування того, яке саме з цих 1 + m + x подій буде мати місце, в силу равновероятности цих подій можна визначити за формулою Н = log 2 (1 + m + х) біт. Таким чином, для виявлення самого факту наявності одиночної помилки і встановлення її позиції необхідно дістати інформацію в кількості не менше Н = log 2 (1 + m + x) біт. Джерелом цієї інформації слугують лише додатково введені x двійкових символів, тому що інші m символів з-за оптимальності кодування до межі зайняті описом самого тексту. Зауважимо, що x двійкових символів у кращому випадку можуть містити інформацію у кількості x біт. Таким чином, при конструюванні коду, що виявляє і виправляє одиночну помилку, слід врахувати, що цього можна домогтися лише при значеннях x, що задовольняють нерівності
х> = log 2 (l + m + x),
або 2 x-x-1> = m.
Рис. 1.Завісімость нижньої межі допустимих значень x від m (суцільна лінія) і залежність відносної надлишковості від m (пунктирна лінія).
Р. Хеммінга розробив конкретну конструкцію коду. яка забезпечує дуже елегантне виявлення та виправлення одиночних помилок при мінімально можливому числі додатково вводяться двійкових символів, тобто при знаку рівності. Простежимо за побудовою цього коду, коли m = 4. З малюнка випливає, що при цьому допустиме значення x дорівнює трьом, тобто при числі основних (інформаційних) двійкових символів m = 4, число додатково введених, тобто контрольних символів має бути не менше трьох. Приймемо, що нам вдалося "обійтися" саме трьома додатковими символами, тобто вдалося сконструювати такий код, за якого кожен з додатково введених трьох символів дає нам максимально можливу кількість інформації, тобто по одному біту. Тоді у розширеному кодовому наборі виявляться сім двійкових символів:
B1B2B3B4 B5B6B7
Оскільки символи B1 - B4 зайняті кодуванням власне тексту, то управляти їх значеннями нам не дано. Що ж стосується символів B5 - B7, то вони призначені саме для виявлення та виправлення помилок і тому їх значення ми можемо пов'язати зі значеннями інформаційних символів довільними трьома функціями від аргументів B1 - B4: B5 = B5 (B1 ,..., B4) (1)
B6 = B6 (B1 ,..., B4) (2)
B7 = B7 (B1 ,..., B4) (3)
такими, щоб в подальшому за допомогою трьох інших функцій від аргументів B1 - B7 e 0 = e 0 (B1-B7) (4)
e 1 = e 1 (B1-B7) (5)
e 2 = e 2 (B1-B7) (6)
визначити значення e 0, e 1, e 2 містять інформацію про те, чи відбулася помилка взагалі і якщо так, то на рівні якого саме з семи символів. Очевидно, є безліч різних варіантів при виборі функцій (1) - (6). Р. Хеммінга поставив перед собою завдання вибору саме такої сукупності функцій (1) - (6), щоб набір значень e 2 e 1 e 0 виявився двійковій записом позиції, де сталася помилка. У випадку ж, коли помилка не мала місця, набір e 2 e 1 e 0 повинен вказати на нульову позицію, тобто на неіснуючий символ B0. З двійкової записи цих позицій 000 (0) 1 0 0 (7)
001 (1) 1 0 1 (8)
010 (2) 1 1 0 (9)
011 (3) 1 1 1 (10)
легко встежити, що значення e 0 "несе відповідальність" за позиції B1, B3, B5 і B7 і тому в якості функції (1.14) береться залежність e 0 = B1 + B3 + B5 + B7 mod 2. (11)
Аналогічно, звертаючи увагу на те, що значення e 1 і e 2 контролюють відповідно B2 B3 B6 B7, B4 B5 B6 B7, отримаємо e 1 = B2 + B3 + B6 + B7 mod 2, (12)
e 2 = B4 + B5 + B6 + B7 mod 2. (13)
Звернемо увагу, що систему (1.14а) - (1.16а) можна розглядати як розгорнуту запис матричного рівняння B1
B2
e 0 1010101 B3
e 1 = 0110011 B4
e 2 0001111 B5
B6
B7
або V e = AV a,
де V e, - вектор помилки, що вказує на її місце розташування; А - основна матриця, стовпці якої суть виконавчі запису чисел від одного до семи.
Операція додавання в усіх трьох рівняннях (14) - (16) здійснюється за модулем два. Підставляючи в систему рівнянні (14) - (16) e 0 = e 1 = e 2 = 0, отримаємо систему з трьох рівнянь
B1 + B1 + B5 + B7 = 0 mod2 (14)
B2 + B3 + B6 + B7 = 0 mod2 (15)
B4 + B5 + B6 + B7 = 0 mod2, (16)
Прийнявши в якості невідомих величини B5, B6 і B7 отримаємо систему з трьох рівнянь з трьома невідомими: B5 + B7 = B1 + B3 mod2, (17)
B6 + B7 = B2 + B3 mod2, (18)
B5 + B6 + B7 = B4 mod2. (19)
Ця система еквівалентна одному матричному рівнянню B1
101 B5 1010 B2
011 B6 = 0110 B3 (20)
111 B7 0001 B4
або CV e = IV i. (21)
де V e і V i, вектори-стовпці, координати яких представлені відповідно контрольними та інформаційними розрядами; С і I - так звані контрольна і інформаційна матриці. Стовпці цих матриць суть виконавчі запису номерів відповідно контрольних та інформаційних розрядів. Рішення системи (17) - (19), або. що те ж саме, матричного рівняння (20) щодо B5, B6, B7 призводить до конкретних виразів для функцій (1) - (3):
B5 = B2 + B3 + B4 mod2, (22)
B6 = B1 + B3 + B4 mod2, (23)
B7 = B1 + B2 + B4 mod2. (24)
Зауважимо, що сам Р. Хеммінга в якості контрольного бере не набір символів B (m +1), B (m +2), ... B (m + x), а нaбор символів, індекси яких представляють цілі ступеня двійки. У випадку, коли число контрольних символів дорівнює трьом, ці індекси дорівнюють 2 0 = 1, 2 1 = 2 і 2 2 = 4, тобто мова йде про набір символів B1B2B4, щодо яких рішення системи (14) - (16) надзвичайно спрощується: B1 = B3 + B5 + B7 mod 2,
B2 = B3 + B6 + B7 mod 2,
B4 = B5 + B6 + B7 mod 2.
Це і природно, оскільки в даному випадку замість (17) маємо справу з матричним рівнянням B3
1 0 0 B1 B5
0 1 0 B2 = B6
0 0 1 B4 B7
де контрольна матриця З завжди дорівнює одиничної матриці. Відзначивши, що при вказаній рекомендації Р. Хеммінга контрольна матриця завжди (незалежно від m і x) виявляється дорівнює одиниці, докладне обговорення цієї рекомендації залишимо на потім, продовжуючи розглядати в якості контрольних B5B6B7 а як інформаційних - B1B2B3B4.
Розглянемо, наприклад, набір інформаційних символів B1B2B3B4 = 1011. За допомогою залежностей (22) - (24) визначимо набір контрольних (додатково введених, надлишкових) символів B5B6B7 = 010. Нехай помилка сталася на рівні символу B5 тобто замість істинного розширеного кодового набору 1011 (0) 10 отримано код 1011 (1) 10. Тоді за допомогою залежностей (14) - (16) знайдемо
e 0 = 1 +1 +1 +0 = 1 mod2,
e 1 = 0 +1 +1 +0 = 0 mod2,
e 2 = 1 +1 +1 +0 = 1 mod2.
Набір значень e 2 e 1 e 0 = 101 є двійковій записом числа "п'ять", тобто вказує саме на п'яту позицію (на символ B5), де, власне, і сталася помилка. Наведена схема Р. Хеммінга з конструювання коду, що виявляє і виправляє одиночну помилку, універсальна, і аналогічний код може бути побудований для довільної пари значень m і x, що задовольняють рівнянню
2 х - х - 1 = m. (25)
Зауважимо також, що зовсім не обов'язково, щоб набір з m інформаційних символів представляв собою код якоїсь певної букви, як це мало місце в тільки що розглянутому прикладі. На практиці спочатку можна здійснити оптимальне (або близьке до оптимального) кодування тексту. Потім вже закодований текст можна ділити на блоки по m двійкових символів у кожному, причому з можливих значень m = 2 x - х - 1 (х = 3, 4, ...) його конкретне значення слід вибирати виходячи з експлуатаційної необхідності. За інших рівних умовах значення m має бути тим меншим, чим більше значення інформації і чим більше рівень перешкод. Після вибору конкретного значення m кожен блок з m інформаційних символів слід нарощувати х = х (m) контрольними символами, призначеними для виявлення і виправлення одиночних помилок в рамках даного блоку. А тепер повернемося до розгляду питання про те, чому Р. Хеммінга в якості контрольних бере саме символи, індекси яких рівні цілим ступенями двійки, тобто 1, 2, 4, 8, 16 ,.... По-перше, як уже йшлося раніше вище, при такому виборі контрольна матриця завжди виявляється дорівнює одиниці, тобто фактично знімається питання вирішення системи (22) - (24) щодо контрольних символів, так як її "рішення" зводиться до простого переписування відповідних рівнянь. Але це не головне, так як систему (22) - (24) доводиться вирішувати тільки один раз і далі при кожному акті кодування ми користуємося лише системою (11) - (13) - рішенням системи (22) - (24) щодо контрольних символів . При реалізації процедур кодування і декодування на ЕОМ сам факт, що контрольні символи роз'єднані (не йдуть підряд один за одним), створює певні незручності при кожному акті кодування і декодування. Природно тому бажання вибрати контрольні символи такими, щоб вони йшли поспіль один за одним, нехай навіть ціною того, щоб один раз вирішити систему (14) - (16). Саме так робили ми, коли всупереч рекомендації Р. Хеммінга взяти в якості контрольних символи B1, B2 і B4 взяли в їх якості символи B5, B6 і B7. Хоча це й змусило нас вирішити систему відносно змінних B5, B6 і B7, але зате при кожному акті кодування і декодування ми змогли оперувати "пачками" контрольних символів, а не "виколупувати" їх серед інформаційних символів.
Виникає питання, а чи завжди, при будь-якій кількості інформаційних символів ми змогли б надходити аналогічним чином? Ні, не змогли б, якщо як і раніше хочемо, щоб двійковий набір символів e x-1, e x-2 ,..., e 0 вказував на адресу помилки. Бо вже коли число контрольних символів більше трьох, ми не маємо права взяти в якості контрольних останні х символів. Легко переконатися, що при цьому контрольна матриця неодмінно була б виродженою, тобто значення її детермінанта виявилася б рівним нулю. Більш того, навіть у розглянутому нами випадку, коли число контрольних символів дорівнює трьом, ми не змогли б в якості контрольних взяти, наприклад, перші три символи. У всіх цих випадках визначники контрольних матриць (згадаємо, що стовпчики цієї матриці суть виконавчі запису номерів обраних нами контрольних символів) виявляються рівними нулю. Нехай, наприклад, ми вибрали в якості контрольних не пачку символів B5, B6, B7, а символи B1, B2, B3. Тоді нам довелося б мати справу з квадратною матрицею третього порядку, стовпці якої є двійковими формами запису чисел 1, 2 і 3:
101
З = 011.
000
Рівність нулю детермінанта цієї матриці свідчить про те, що систему (1.14б) - (1.16б) не можна вирішити відносно змінних B1, B2, B3. Таким чином, при виборі серед m + x символів x контрольних слід дбати про те, щоб визначник контрольної матриці порядку x, стовпці якої є виконавчі запису номерів вибраних символів, не виявився рівним нулю. Саме щоб позбутися від цих турбот, Р. Хеммінга рекомендує в якості контрольних взяти символи з індексами I, 2, 4, 8 і т.д. Легко виявити, що при такому виборі контрольних символів ми завжди (незалежно від їх числа) будемо мати справу з одиничною матрицею.
Крім залежності (10). на малюнку приведена також залежність відносної надлишковості від m. Легко помітити, що зі збільшенням m потрібний процент надмірності для виявлення та виправлення одиночної помилки різко зменшується. Настільки неприродний результат є наслідком штучного, далекого від реальності допущення, що в рамках кожного кодового набору незалежно від його довжини m + x може відбутися не більше однієї помилки. Якщо ж припустити можливість двох і більше помилок, то завдання їх виявлення, і тим більше виправлення ускладнюється. Побудувати для цих випадків коди настільки ж елегантні, як код Р. Хеммннга для одиночної помилки, поки не вдалося.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа,
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок,
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс»,