B B парності В

Рис.4. Кодування числа 1100 (а); додаються біти парності (б); помилка в секторі АС (в)

Далі додамо біт парності до кожного з трьох порожніх секторів, щоб вийшла позитивна парність, як показано на рис.3.4,б. По визначенню сума бітів у кожному із трьох кіл, А, В, і С, повинна бути парною. У колі А знаходиться 4 числа: 0, 0, 1 і 1, що у сумі дають парне число 2. У колі В знаходяться числа 1, 1, 0 і 0, що також при додаванні дають парне число 2. Те ж і для кола С. У даному прикладі вийшло так, що всі суми однакові, але взагалі можливі випадки із сумами 0 і 4. Малюнок відповідає кодованому слову, що складається з 4 бітів даних і 3 бітів парності.

Припустимо, що біт у секторі АС змінився з 0 на 1, як показано на рис.3.4, в. Комп'ютер бачить, що кола А і С мають негативну парність. Єдиний спосіб виправити помилку, змінивши тільки один біт, – повернення бітові АС значення 0. Таким способом комп'ютер може виправляти одиночні помилки автоматично.

А тепер розглянемо використання алгоритму Хеммінгу при створенні кодів з виправленням помилок для слів будь-якого розміру. У коді Хеммінга до слова, що складається з m бітів, додається r бітів парності, при цьому утвориться слово довжиною m+r бiтiв. Біти нумеруються з одиниці (а не з нуля), причому першим вважається крайній лівий. Усі біти, номери яких – ступенi двійки, є бітами парності; інші використовуються для даних. Наприклад, до 16-бітного слова потрібно додати 5 бiтiв парності. Біти з номерами 1, 2, 4, 8 і 16 – біти парності, а всі інші – біти даних. Усього слово містить 21 біт (16 бiтiв даних і 5 бiтiв парності). У розглянутому прикладі будемо використовувати позитивну парність (вибір довільний).

Кожен біт парності перевіряє визначені бітові позиції. Загальне число бiтiв зі значенням 1 у позиціях, що перевіряються, повинне бути парним. Нижче зазначені позиції перевірки для кожного біта парності:

Біт 1 перевіряє біти 1, 3, 5, 7, 9,11,13,15, 17, 19, 21.

Біт 2 перевіряє біти 2, 3, 6, 7, 10, 11, 14,15, 18, 19.

Біт 4 перевіряє біти 4,5, 6,7,12,13,14,15,20, 21.

Біт 8 перевіряє біти 8, 9, 10,11,12,13, 14, 15.

Біт 16 перевіряє біти 16,17,18,19,20, 21.

У загальному випадку біт b перевіряється бітами Ьь D2,..., Ь,, такими що bi+b₂+..,+bj-b. Наприклад, біт 5 перевіряється бітами 1 і 4, оскільки 1+4=5. Біт 6 перевіряється бітами 2 і 4, оскільки 2+4-6 і т.д.

На Рис. 2.12 показана побудова коду Хэмминга для 16-бітного слова 1111000010101110. Відповідним 21-бітним кодованим словом є 001011100000101101110. Щоб побачити, як відбувається виправлення помилок, розглянемо, що відбудеться, якщо біт 5 змінить значення через різкий стрибок напруги на лінії електропередачі. У результаті замість кодованого слова 001011100000101101110 вийде 001001100000101101110. Будуть перевірені 5 бітів парності. От результати перевірки:

Біт парності 1 неправильний (біти 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 містять п'ять одиниць).

Біт парності 2 правильний (біти 2,3,6,7,10,11,14,15,18,19 містять шість одиниць).

Біт парності 4 неправильний (біти 5,6,7,12,13,14,15,20,21 містять п'ять одиниць).

Біт парності 8 правильний (біти 8,9,10,11,12,13,14,15 містять дві одиниці).

Біт парності 16 правильний (біти 16,17,18,19,20,21 містять чотири одиниці).

Загальне число одиниць у бітах 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 і 21 повинно бути парним, оскільки в даному випадку використовується позитивна парність. Неправильним повинний бути один з бітів, що перевіряються бітом парності 1 (а саме 1, 3,5,7,9,11,13,15,17,19 і 21). Біт парності 4 теж неправильний. Це значить, що змінив значення один з наступних бітів: 4,5,6,7,12,13,14,15,20, 21. Помилка повинна бути в біті, що утримується в обох списках. У даному випадку загальними є біти 5,7,13,15 і 21. Оскільки біт парності 2 правильний, біти 7 і 15 виключаються. Правильність біта парності 8 виключає наявність помилки в біті 13. Нарешті, біт 21 також виключається, оскільки біт парності 16 правильний. У підсумку залишається біт 5, у якому й утримується помилка. Оскільки цей біт має значення 1, він повинний прийняти значення 0. Саме в такий спосіб виправляються помилки.

Щоб знайти неправильний біт, спочатку потрібно підрахувати всі біти парності. Якщо вони правильні, помилки немає (або є, але більше однієї). Якщо виявилися неправильні біти парності, то потрібно скласти їхнього номера. Сума, отримана в результаті, дасть номер позиції неправильного біта. Наприклад, якщо біти парності 1 і 4 неправильні, а 2,8 і 16 правильні, то помилка відбулася в біті 5 (1+4).

Поиск по сайту: