Учебное пособие: Компаратори слів, перетворювачі кодів та схеми контролю

Контрольні біти k_i розташовують у послідовності інформаційних бітів u_j на позиціях із номерами 2^i-1 , як показано у табл. 5.

Таблиця 5

Позиція	1	2	3	4	5	6	7
	001	010	011	100	101	110	111
Біт	k1	k2	u1	k3	u2	u3	u4

Значення перевірних бітів k_i обчислюється додаванням за модулем 2 значень бітів, у двійковому виразі номерів яких наявна одиниця в i -му розряді. Відповідно, для обчислення значення k₁ потрібно додати за модулем 2 значення бітів із непарними номерами:

.

Для визначення k₂ треба додати за модулем 2 біти, у двійковому виразі номерів яких наявна одиниця у другому розряді, тобто:

.

Контрольний біт k₃ визначається додаванням за модулем 2 бітів, у двійковому виразі номерів яких наявна одиниця у третьому розряді:

.

Схема перетворювача чотирирозрядних кодових слів у код Хеммінга зображена на рис. 7.

Визначення та виправлення помилок здійснюється k перевірками. При кожній перевірці додаються за модулем 2 біти прийнятої послідовності інформаційних та контрольних розрядів, двійкові номера яких мають одиницю в першому, другому і так далі розрядах. Якщо під час передавання не було збою, то результати всіх перевірок дорівнюють нулю. Якщо збій відбувся, то хоча б одна перевірка не дорівнює нулю. У цьому випадку треба сформувати кодову комбінацію з результатів перевірок, який вкаже на розряд, де відбувся збій (він має назву синдром). Молодший розряд коду результатів перевірок формує перша перевірка, старший – остання. Інверсія біта в розряді з одержаним номером виправить помилку.

Рис. 7. Схема перетворювача чотирирозрядних кодових слів в код Хеммінга

Наприклад, необхідно сформувати код Хеммінга, що виявляє та виправляє одноразові помилки у послідовності:

1	1	0	0
u1	u2	u3	u4

Відповідно,

Послідовність, що закодована кодом Хеммінга, буде мати вигляд:

0	1	1	1	1	0	0
k1	k2	u1	k3	u2	u3	u4

Нехай після передачі відбувся збій в одному розряді і прийнята послідовність 0110100 (помилка в четвертому розряді – k₃ ). Тоді перша та друга перевірки дадуть значення 0, а третя – 1:

Код 100, що створюють результати перевірок, вказує, що відбувся збій у четвертому розряді. Якщо проінвертувати четвертий розряд, то одержимо виправлену послідовність 0111100.

Із розглянутого прикладу видно, що схема пристрою контролю повинна містити такі складові частини: схеми згортки (елементи „виключне АБО”) відповідно кількості перевірок, що виконуються; дешифратор, який на основі отриманого синдрому керує інверсією помилкового розряду та елементів, що виконують саму інверсію. Така схема зображена на рис. 16 (схеми згортки позначені прямокутником з написом 2k + 1 ). У якості „керованих інверторів” у схемі використовуються суматори за модулем 2.

k1 k2 u1 k3 u2 u3 u4

Вихідний код

Рис. 16. Схема пристрою контролю