Автор работы: Пользователь скрыл имя, 18 Декабря 2013 в 19:30, реферат
Шифрування – це кодування даних з метою захисту від несанкціонованого доступу. Процес кодування називається шифруванням, а процес декодування – розшифруванням. Саме кодоване повідомлення називається шифрованим, а застосований метод називається шифром. Основна вимога до шифру полягає в тому, щоби розшифрування (і, можливо, шифрування) були можливі тільки при наявності санкцій, тобто деякої додаткової інформації (або пристрою), яка називається ключем шифру.
Процес декодування шифровки без ключа називається дешифруванням. Галузь знань про шифри, методи їх побудови та розкриття називається криптографією. Властивість шифру протистояти розкриттю називається криптостійкістю або надійністю і звичайно визначається складністю алгоритму дешифровки. У практичній криптографії криптостійкість шифру оцінюється з економічних міркувань.
1. Bci символи коду Хемінга з номерами розрядів розташовують в порядку збільшення номерів i під ними записують номери розрядів в двійковому коді
а1 а 2 а3 а4 а5 а6 а7
0001 0010 0011 0100 0101 0110 0111
2. Перше перевірне рівняння складають як суму за mod 2 вcix розрядів, в номерах яких в молодшому розряді 20 стоїть одиниця: .
Друге перевірне рівняння складають як суму за mod 2 вcix розрядів, в номерах яких стоїть одиниця на другому місці відповідного двійкового еквівалента (2І): .
Третє перевірне рівняння складають як суму за mod 2 всіх розрядів, в номерах яких стоїть одиниця на третьому місці (22): .
Аналогічно утворюються i інші перевірні суми (при більшій кількості інформаційних i контрольних символів, відповідно).
Як видно з наведених рівнянь, в кожну перевірну суму входить тільки один невизначений контрольний символ kі (а1, а2, а4, відповідно), а вci інші інформаційні символи відомі
Bci перевірні рівняння за умовою Хемінга повинні дорівнювати 0 при підсумовуванні за mod 2. 3 цієї умови i знаходять контрольні символи.
Наприклад, необхідно передати інформаційну кодову комбінацію:
а1 а2 а3 а4
1 1 0 0
з числом розрядів n 0 = 4.
З формули 2k ?n +1 = n0+k +1 визначимо, що k =3. Запишемо перевірні суми:
;
;
.
Підставимо у рівняння значення відомих інформаційних символів. З умови piвності нулю вcix перевірних сум визначаємо відповідно контрольні символи. З першого рівняння а0 = 0, з другого а1 = 1, з третього а4 = 1.
Відповідно буде передана така комбінація:
яка є комбінацією коду Хемінга.
Алгоритм декодування коду Хемінга
На приймальному пристрої комбінація коду Хемінга декодується -визначається наявність спотворення прийнятої кодової комбінації i, якщо один символ комбінації спотворений, він автоматично спочатку визначається, а потім виправляється. Визначення i виправлення спотвореного символу здійснюється на основі перевірних рівнянь. При правильному прийомі всі суми повинні дорівнювати нулю. В разі спотворення двійкове число, яке є результатом цих сум (синдром помилки), переводять в десяткове число, яке вказує номер спотвореного символу, який в подальшому виправляється шляхом інвертування.
Наприклад, при прийомі закодованої вище неспотвореної кодової комбінації Хемінга:
значення вcix символів комбінації підставляють на відповідні місця у перевірних сумах:
;
;
.
Ознака правильно прийнятої комбінації – рівність нулю вcix сум.
Припустимо, що шостий символ кодової комбінації спотворений, тобто замість комбінації 0111100 буде прийнята:
а1 а 2 а 3 а 4 а6 а7 а8
0 1 1 1 1 1 0
Підставимо значення прийнятих символів у перевірні рівняння.
Одержимо: ;
;
.
Переведемо двійкове число (синдром) в десяткове. Одержимо десяткове число 6, яке i вказує на номер спотвореного символу.
Кодер коду Хемінга
На основі наведених вище правил будується кодер коду Хемінга (рис. 5.15). Bін автоматично визначає значення контрольних cимвoлiв коду при відомих інформаційних, які складаються з безнадлишкових комбінацій звичайного двійкового коду.
Рисунок 5.15 – Кодер коду Хемінга
На входи cyматорів за mod 2 Ul, U2, U3 подаються інформаційні символи відповідно до перевірних сум. На вході суматорів одержуються контрольні символи а1, а2, а4. Інформаційні i контрольні символи розташовуються в необхідному порядку i через шину виводяться для подальшого перетворення.
Декодер коду Хемінга
Декодер коду Хемінга (рис. 5.16) аналізує прийняту кодову комбінацію i в разі спотворення будь-якого одного символу (інформаційного чи контрольного) автоматично виправляє спотворений символ.
Вхідна комбінації коду Хемінга надходить на суматори за mod 2 U1-U3 відповідно до контрольних сум. На виходах суматорів утворюється результат контрольних сум S1-S3. При правильному прийомі суми SI, S2, S3 повинні дорівнювати нулю.
В разі спотворення одного символу на виходах елементів U1-U3 з'явиться двійкова кодова комбінація (синдром помилки), яка декодується декодером U4. На одному з виходів декодера з'являється рівень логічної одиниці, який відповідає номеру спотвореного символу.
Рисунок 5.16 – Декодер коду Хемінга для семиелементної комбінації
На суматори за mod 2 U5-U8 надходять відповідні сигнали з входів а3, а5, а6, а7 (інформаційні символи) i відповідний вихід декодера.
При правильному прийомі на виходах 1-7 декодера - логічні нулі i на виходах суматорів U5-U8 з'являться інформаційні символи а3, а5 , а6 , а7 без змін.
В разі спотворення одного з символів, наприклад, третього, на третьому виході декодера з'явиться рівень логічної одиниці i на виході суматора за mod2 U5 спотворений символ автоматично інвертується, перетворюючись у правильний.