| Главная » Файлы » Контрольные работы » Контрольные работы |
Захист та завадостійка обробка дани
| [ Скачать с сервера (166.0 Kb) ] | 04.04.2017, 14:09 |
| Код Хеммінга Код Хеммінга – це алгоритм, який дозволяє закодувати будь-яке інформаційне повідомлення певним чином і після передачі (наприклад, по мережі) визначити, чи з’явилася якась помилка в цьому повідомленні (наприклад, через перешкоди) і при можливості відновити це повідомлення. Нижче описаний алгоритм, який може виправляти лише одну помилку. Код Хеммінга складається з двох частин. Перша частина кодує вихідне повідомлення, вставляючи в нього в певних місцях контрольні біти (вирахувані особливим чином). Друга частина отримує вхідне повідомлення і заново вираховує контрольні біти (по тому ж алгоритму, що й перша частина). Якщо всі заново вирахувані контрольні біти співпадають з отриманими, то повідомлення отримане без помилок. В іншому випадку, виводиться повідомлення про помилку і при можливості помилка виправляється. Вхідне повідомлення «БАРТИШ», яке необхідно передати без помилок. Для цього спочатку потрібно представити його в бінарному виді. Символ ASCII код Бінарне представлення Р 207 11001111 У 192 11000000 С 194 11000010 Е 203 11001011 Ц 197 11000101 К 205 11001101 И 202 11001010 Й 206 11001110 На цьому етапі слід визначити довжину інформаційного слова. Припустимо, що довжина слова буде рівна 16. Таким чином необхідно розділити вихідне повідомлення на блоки по 16 біт, які будемо потім кодувати окремо один від одного. Так як один символ займає в пам’яті 8 біт, то в одне закодоване слово поміщається рівно два ASCII символа. Отримаємо чотири бінарні рядки по 16 біт: Р У С Е Ц К И Й 11001111 11000000 11000010 11001011 11000101 11001101 11001010 11001110 Після цього процес кодування розпаралелюється і чотири частини повідомлення («ПА», «ВЛ», «ЕН» і «КО») кодуються незалежно одна від одної. Перш за все потрібно вставити контрольні біти. Вони вставляються в позиціях з номерами, рівними степеням двійки. В нашому випадку (при довжині інформаційного слова в 16 біт) це будуть позиції 1, 2, 4, 8, 16. Відповідно вийшло 5 контрольних біт. Р У 001010001111 110000000 С Е 001010000010 110001011 Ц К 001010000101 110001101 И Й 001010001010 110001110 Таким чином довжина повідомлення збільшилася на 5 біт. До вирахування самих контрольних біт, їм присвоюється значення «0». Значення кожного контрольного біта залежить від значень інформаційних біт, які цей контрольний біт контролює. Контрольний біт з номером N контролює всі наступні N біт через кожні N біт, починаючи з позиції N. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 х х х х х х х х х х х 1 х х х х х х х х х х 2 х х х х х х х х х х 4 х х х х х х х х 8 х х х х х х 16 Знаком «х» позначені ті біти, значення яких контролює контрольний біт, номер якого праворуч. Тобто, наприклад, біт номер 12 контролюється бітами з номерами 4 і 8. Для того, щоб дізнатися, якими бітами контролюється біт з номером N потрібно розкласти N по степеням двійки. Значення контрольних біт вираховується таким чином: береться кожен контрольний біт і рахується скільки серед контрольованих ним бітів одиниць, якщо їх кількість парна, то ставимо нуль, в протилежному випадку – одиницю. Можна і навпаки, головне, щоб в «кодуючій» і «декодуючій» частинах алгоритм був однаковий. Р У 001010001111 110000000 Вираховуємо контрольні біти для повідомлення: С Е 001010000101 110001101 Ц К 001010000010 110001011 И Й 001010001010 110001110 На цьому перша частина алгоритму завершується. Р У 101010001101 110000000 Припустимо, що отримали закодоване першою частиною алгоритму повідомлення, але воно прийшло з помилкою. Наприклад, 11-й біт передався невірно: Друга частина алгоритму заклечається в тому, що необхідно заново вирахувати всі контрольні біти і порівняти їх з контрольними бітами, які отримали. Порахувавши контрольні біти з невірним 11-м бітом отримаємо: Р У 011010001101 110000000 Контрольні біти під номерами 1, 2 і 8 не співпадають з такими ж контрольними бітами, які отримали. Додавши номера позицій невірних контрольних біт (1 + 2 + 8 = 11) отримаємо позицію помилкового біта. Інвертувавши його і відкинувши контрольні біти, отримаємо вихідне повідомлення у первозданному вигляді. Аналогічно відбувається і з 2, 3 частинами повідомлення. В даній версії алгоритму на одне інформаційне слово можна виправити лише одну помилку. Код Хаффмана Алгоритм Хаффмана – алгоритм оптимального префіксного кодування алфавіту. Використовується в багатьох програмах стиснення даних. Спочатку складається список кодованих символів, при цьому один символ розглядається як дерево, яке складається із одного елементу з вагою рівною частоті виникнення символу в тексті. Із списку вибирається два вузли з найменшою вагою. Формується новий вузол з вагою рівною сумі ваг вибраних вузлів і приєднуються до нього два вибрані вузли в якості дочірніх. Додається до списку щойно сформований вузол. Якщо в списку більше одного вузла, то повторюються операції для двох вузлів. Закодуємо повідомлення «БАРТИШ». В даному випадку всі символи мають однакову частоту виникнення, кожен символ зустрічається 1 раз. Щоб отримати код символу, потрібно, починаючи з кореня дерева йти донизу до листка відповідного даному символу. При цьому слід записувати ті значення, які написані на дугах, через які проходимо. Отримані коди: Р 1111 У 1110 С 1101 Е 1100 Ц 100 К 101 И 00 Й 01 В даному випадку всі символи мають однакову вагу, проте для більших повідомлень символи, що часто зустрічаються, матимуть коди коротші. Закодований рядок матиме вигляд: 1111111011011100100101001 і займає 25 біт (при кодуванні ASCII довжина рядка займала б 80біт). | |
| Просмотров: 489 | Загрузок: 12 | Рейтинг: 0.0/0 | |
| Всего комментариев: 0 | |