Двійкова арифметика без урахування переносів

 

Залишимо поліноми поза полем нашої уваги, і сфокусуємось на звичайній арифметиці, так як дії, що виконуються під час обчислення контрольної суми, є арифметичними операціями без урахування переносів. Ця арифметична система є ключовою частиною розрахунків CRC.

Додавання двох чисел в CRC арифметиці повністю аналогічно звичайному арифметичній дії за винятком відсутності переносів з розряду в розряд. Це означає, що кожна пара бітів визначає результат свого розряду незалежно від результатів інших пар.

Наприклад:

					1	0	0	1	1	0	1	1
				+	1	1	0	0	1	0	1	0
					0	1	0	1	0	0	0	1

Для кожної пари бітів можливі 4 варіанти:

 

				0	+	0	=	0
				0	+	1	=	1
				1	+	0	=	1
				1	+	1	=	0	()

 

Те ж саме справедливо і для віднімання:

 

					1	0	0	1	1	0	1	1
				–	1	1	0	0	1	0	1	0
					0	1	0	1	0	0	0	1

 

коли є також 4 можливі комбінації:

 

				0	–	0	=	0
				0	–	1	=	1	()
				1	–	0	=	1
				1	–	1	=	0

 

Фактично, як операція додавання, так і операція віднімання в CRC арифметиці ідентичні операції "Виключне АБО" (eXclusive OR – XOR), що дозволяє замінити 2 операції першого рівня (додавання і віднімання) однією дією, яка одночасно, виявляється інверсним самому собі. Дуже зручна властивість такої арифметики.

Згрупувавши додавання і віднімання в одну єдину дію, CRC арифметика виключає із поля своєї уваги всі величини, що лежать за межами самого старшого свого біта. Хоча абсолютно ясно, що значення 1010 більше, ніж 10, це виявляється не так, коли кажуть, що 1010 повинно бути більше, ніж 1001.

Щоб зрозуміти чому, спробуємо отримати з 1010 значення 1001, віднявши або додавши до нього одну і ту ж величину:

 

							1	0	1	0
						+	0	0	1	1
							1	0	0	1
							1	0	1	0
						–	0	0	1	1
							1	0	0	1

 

Це зводить нанівець всяке уявлення про порядок. Визначивши дію складання, перейдемо до множення і ділення. Множення, як і у звичайній арифметиці, вважається сумою значень першого співмножника, зсунутих у відповідності зі значенням другого співмножника.

 

				1	1	0	1
			х	1	0	1	1
				1	1	0	1
CRC+			1	1	0	1	.
		0	0	0	0	.	.
	1	1	0	1	.	.	.
	1	1	1	1	1	1	1

 

Звернемо увагу: при підсумовуванні використовується CRC складання.

Ділення трохи складніше, тому що потрібно знати, коли "одне число перетворюється в інше". Щоб зробити це, необхідно ввести слабке поняття розмірності: число X більше або дорівнює Y, якщо позиція самого старшого одиничного біта числа X більш значуща (або відповідає) позиції самого старшого одиничного біта числа Y. Приклад розподілу наведено на рис.1.4.

1	1	0	1	0	1	1	0	1	1	0	0	0	0	1	0	0	1	1
1	0	0	1	1	↓	↓	↓	↓	↓	↓	↓	↓	↓	1	1	0	0	0	0	1	0	1	0
0	1	0	0	1	1	1	0	1	1	0	0	0	0
→	1	0	0	1	1	↓	↓	↓	↓	↓	↓	↓	↓	1
=	0	0	0	0	0	1	0	1	1	0	0	0	0
	→	1	0	0	1	1					↓	↓	↓	0
		→	1	0	0	1	1				0
			→	1	0	0	1	1			0
				→	1	0	0	1	1		0
					→	1	0	0	1	1	1
					=	0	0	1	0	1	0	0	0
						→	1	0	0	1	1		↓	0
							→	1	0	0	1	1	1
							=	0	0					Залишок від CRC ділення
								→	1	0	0	1	1	0

 

Рис.1.4 — Схема розподілу біт при діленні у двійковій системі числення

 

Знаючи, що дії додавання і віднімання в нашій арифметиці – це одне і те ж саме. У такому випадку, A+0=A i A–0=A.

Якщо число A отримано множенням числа B, то в CRC арифметиці це означає, що існує можливість сконструювати число A з нуля, застосовуючи операцію XOR до числа B, зсунутому, на різну кількість позицій. Наприклад, якщо A дорівнює 0111010110, а B – 11, то можна сконструювати A з B наступним чином:

 

Табл.1.1 — Конструкція отримання числа за допомогою операції XOR

 

			А	0	1	1	1	0	1	0	1	1	0
			=	0	0	0	0	0	0	0	1	1	0
			+	0	0	0	0	1	1	0	0	0	0
			+	0	0	0	1	1	0	0	0	0	0
			+	0	1	1	0	0	0	0	0	0	0

 

Однак, якщо б А дорівнювало б 0111010111, то не вдалося скласти його за допомогою різних зсувів числа тому говорять, що в CRC арифметиці воно не ділиться на B.

Таким чином, видно, що CRC арифметика зводиться здебільшого до операції "Виключне АБО" деякого значення при різних величинах зсуву.

Визначивши всі правила CRC арифметики, тепер можна охарактеризувати обчислення CRC як просте ділення, чим воно фактично і є.

Щоб виконати обчислення CRC, необхідно вибрати дільник. Кажучи математичною мовою, дільник називається генераторним поліномом, або просто поліномом, і це ключове слово будь-якого CRC алгоритму. Для простоти будемо називати CRC поліном просто поліномом. Можна вибрати і використовувати в CRC будь-який поліном. Ступінь полінома W (Width – ширина) (позиція самого старшого одиничного біта) надзвичайно важлива, бо від неї залежать всі інші розрахунки. Зазвичай вибирається ступінь 16 або 32, так як це полегшує реалізацію алгоритму на сучасних комп'ютерах. Ступінь полінома – це дійсна позиція старшого біта, наприклад, ступінь полінома 10011 дорівнює 4, а не 5.

Ступінь (Width) – Ступінь (або ширина) CRC алгоритму відповідає ступеню використовуваного полінома (або довжині полінома мінус одиницю). Наприклад, якщо використовується поліном 11010, то ступінь алгоритму дорівнює 4. Зазвичай використовується ступінь, кратна 8.

Вибравши поліном приступимо до розрахунків. Це буде просте ділення, у термінах CRC арифметики, повідомлення на наш поліном. Єдине, що треба буде зробити до початку роботи, так це доповнити повідомлення нульовими W бітами.

Первинне повідомлення: 1101011011

Поліном: 10011

Повідомлення, доповнене W бітами: 1101011011 0000

Тепер просто поділимо повідомлення на поліном, використовуючи правила CRC арифметики. Раніше вже розглядалася це дія.

 

1	1	0	1	0	1	1	0	1	1	0	0	0	0	1	0	0	1	1
1	0	0	1	1	↓	↓	↓	↓	↓	↓	↓	↓	↓	1	1	0	0	0	0	1	0	1	0
0	1	0	0	1	1	1	0	1	1	0	0	0	0
→	1	0	0	1	1	↓	↓	↓	↓	↓	↓	↓	↓	1
=	0	0	0	0	0	1	0	1	1	0	0	0	0
	→	1	0	0	1	1					↓	↓	↓	0
		→	1	0	0	1	1				0
			→	1	0	0	1	1			0
				→	1	0	0	1	1		0
					→	1	0	0	1	1	1
					=	0	0	1	0	1	0	0	0
						→	1	0	0	1	1		↓	0
							→	1	0	0	1	1	1
							=	0	0					Залишок від CRC ділення
								→	1	0	0	1	1	0

 

Рис.1.5 — Схема ділення з використанням правил CRC арифметики

 

В результаті отримуємо частку, яка нас не цікавить, і тому, відкидається за непотрібністю, і залишок, який використовується в якості контрольної суми. Розрахунок закінчено. Як правило, контрольна сума додається до повідомлення і разом з ним передається по каналах зв'язку. У нашому випадку буде передано наступне повідомлення:

 

1101011011 + 1110 → 11010110111110

 

На іншому кінці каналу приймач може зробити одне з рівноцінних дій:

1. Виділити текст повідомлення, обчислити для нього контрольну суму (не забувши при цьому доповнити повідомлення W бітами), і порівняти її з переданою.

2. Обчислити контрольну суму для всього надісланого повідомлення (без додавання нулів), і подивитися, чи вийде в результаті нульовий залишок.

Обидва ці варіанти абсолютно рівноправні.

Таким чином, при обчисленні CRC необхідно виконати наступні дії:

1. Вибрати ступінь полінома W і поліном G ступеня (W).

2. Додати до повідомлення нульові W біти. Назвемо отриманий рядок M'.

3. Поділити M' на G з використанням правил CRC арифметики. Отриманий залишок і буде контрольною сумою.

Треба відзначити, що передане повідомлення T є добутком полінома. Щоб зрозуміти це, звернемо увагу, що а) останні W біти повідомлення – це залишок від ділення доповненого нулями вихідного повідомлення на обраний поліном, і б) складання рівносильне відніманню, тому збільшення залишку доповнює значення повідомлення до наступного повного добутку. Якщо повідомлення при передачі було пошкоджено, то отримаємо повідомлення T_E, де E – це вектор помилки, а '_' – це CRC складання (або операція XOR). Отримавши повідомлення, приймач ділить T_E на G. Так як T mod G = 0, (T_E) mod G = E mod G. Отже, якість полінома, який обираємо для перехоплення деяких певних видів помилок, буде визначатися набором добутків G, так як у разі, коли E також є добутком G, така помилка виявлена не буде. Отже, наше завдання полягає в тому, щоб знайти такі класи G, добутки яких будуть як можна менш схожі на шуми в каналі передачі (які і викликають пошкодження повідомлення). Розглянемо, які типи шумів в каналі передачі можна очікувати.

Однобітові помилки. Така помилка означає, що E=1000...0000. Можна гарантувати, що помилки цього класу завжди будуть розпізнані за умови, що в G принаймні 2 біта встановлені в "1". Будь-який добуток G може бути сконструйований операціями зсуву та складання, і водночас, не вдається отримати значення з 1 одиничним бітом зсовуючи і складаючи величину, яка має більше 1 одиничного біта, так як в результаті завжди будуть присутні принаймні 2 біта.

Двохбітові помилки. Для виявлення будь-яких помилок виду 100...000100...000 (тобто коли E містить принаймні 2 одиничних біта) необхідно вибрати таке G, яке б не мало множників 11, 101, 1001, 10001, і так далі. Такі поліноми повинні існувати – поліном з одиничними бітами в позиціях 15, 14 і 1, який не може бути дільником жодного числа менше 1...1, де "..." 32767 нулів.

Помилки з непарною кількістю біт. Може перехопити будь-які пошкодження, коли E має непарне число біт, вибравши поліном G таким, щоб він мав парну кількість біт. а) CRC множення є простою операцією XOR постійного регістрового значення з різними зсувами; б) XOR – це лише операція перемикання бітів; і в) якщо застосовується в регістрі операція XOR до величини з парною кількістю біт, парність кількості одиничних бітів у регістрі залишиться незмінною. Наприклад, почнемо з E=111 і спробуємо скинути всі 3 біти в "0" послідовним виконанням операції XOR з величиною 11 і одним з варіантів зсуву (тобто, "E=E XOR 011" і "E=E XOR 110"). Це аналогічно задачі про перевертання склянок, коли за одну дію можна перевернути одночасно будь-які дві склянки. Більшість популярних CRC поліномів містять парну кількість одиничних бітів.

Пакетні помилки. Пакетна помилка виглядає як E=000...000111...11110000...00, тобто E складається з нулів за винятком групи одиниць десь в середині. Цю величину можна перетворити E=(10000...00)(1111111...111), де є z нулів у лівій частині та n одиниць у правій. Для виявлення цих помилок необхідно встановити молодший біт G в 1. При цьому необхідно, щоб ліва частина не була множником G. При цьому завжди, поки G ширше правій частині, помилка завжди буде розпізнана.

 

Табл.1.2 — Розповсюдженні поліноми

 

16 біт	(16,12,5,0)	стандарт "X25"
(16,15,2,0)	"CRC 16"
32 біт	(32,26,23,22,16,12,11,10,8,7,5,4,2,1,0)	Ethernet

 

КОД ХЕММІНГА

Припустимо, що слово складається з m бітів даних, до яких додаємо р додаткових бітів (контрольних розрядів). Нехай загальна довжина слова буде n (n-m+р). п-бітову одиницю, що містить m бітів даних і р контрольних розрядів, часто називають кодованими словом. Для будь-яких двох кодованих слів, наприклад 10001001 і 10110001, можна визначити, скільки відповідних бітів у них відрізняється. У даному прикладі таких біта три. Щоб визначити кількість відмінних бітів, потрібно над двома кодованими словами виконати логічну операцію ВИКЛЮЧНЕ АБО й порахувати кількість бітів зі значенням 1 в отриманому результаті. Число бітових позицій, по яких розрізняються два слова, називається інтервалом Хеммінга. Якщо інтервал Хеммінга для двох слів дорівнює d, це означає, що достатньо d бітових помилок, щоб перетворити одне слово в інше. Наприклад, інтервал Хеммінга кодованих слів 11110001 і 00110000 дорівнює 3, оскільки для перетворення першого слова в друге досить 3 помилок у біт. Пам'ять складається з m-бітних слів, і, отже, існує 2^m варіантів поєднання бітів. Кодовані слова складаються з n бітів, але через спосіб підрахунку контрольних розрядів припустимі тільки 2^т з 2" кодованих слів. Якщо у пам'яті виявляється неприпустиме кодоване слово, комп'ютер знає, що сталася помилка. При наявності алгоритму для підрахунку контрольних розрядів можна скласти повний список доступних кодованих слів і з цього списку знайти два слова, для яких інтервал Хеммінга буде мінімальним. Це інтервал Хеммінга повного коду. Властивості перевірки і виправлення помилок певного коду залежать від його інтервалу Хеммінга. Щоб виявити d помилок у бітах, необхідний код з інтервалом d+1, оскільки d помилок не можуть змінити одне допустиме кодоване слово на інше допустиме кодоване слово. Відповідно, щоб виправити d помилок у бітах, необхідний код з інтервалом 2d+l, оскільки в цьому випадку допустимі кодовані слова так сильно відрізняються один від одного, що навіть якщо станеться d змін, початкове кодоване слово буде ближче до помилкового, ніж будь-яке інше кодоване слово, тому його легко можна буде визначити.

В якості простого прикладу коду з виявленням помилок розглянемо код, в якому до даних приєднується один біт парності. Біт парності вибирається таким чином, що число бітів зі значенням 1 в кодованому слові парне (або непарне). Інтервал цього коду дорівнює 2, оскільки будь-яка помилка в бітах призводить до кодованого слова з неправильною парністю. Іншими словами, достатньо двох помилок у бітах для переходу від одного допустимого кодованого слова до іншого допустимого слова. Такий код може використовуватись для виявлення одиночних помилок. Якщо з пам'яті зчитується слово, що містить неправильну парність, надходить сигнал про помилку. Програма не зможе продовжуватись, але зате не буде невірних результатів.

В якості простого прикладу коду з виправленням помилок розглянемо код з чотирма допустимими кодованими словами:

 

0000000000, 0000011111, 1111100000 і 1111111111

 

Інтервал цього коду дорівнює 5. Це означає, що він може виправляти подвійні помилки. Якщо з'являється кодоване слово 0000000111, комп'ютер знає, що початкове слово повинно бути 0000011111 (якщо сталося не більше двох помилок). При наявності трьох помилок, якщо, наприклад, слово 0000000000 змінилося на 0000000111, цей метод не допускається. Уявімо, що хочемо розробити код m з бітами даних і р контрольних розрядів, який дозволив би виправити всі помилки в бітах. Кожне з 2^r допустимих слів має n неприпустимих кодованих слів, які відрізняються від допустимого одним бітом. Вони утворюються інвертуванням кожного з n бітів n-бітовому кодованому слові. Отже, кожне з 2^r допустимих слів вимагає п+1 можливих поєднань бітів, які приписуються цьому слову (п можливі помилкові варіантів і один правильний). Оскільки загальна кількість різних поєднань бітів дорівнює 2ⁿ, то (n+l) 2^m < 2ⁿ.

Оскільки n=m+r, отже, (m+r+1)< 2^r. Ця формула дає нижню межу числа контрольних розрядів, необхідних для виправлення одиничних помилок. У табл. 1.3 показано необхідну кількість контрольних розрядів для слів різного розміру.

 

Табл.1.3 – Розмірність коду

Розмір слова	Кількість контрольних розрядів	Загальний розмір	% збільшення довжини слова

 

Цієї теоретичної нижньої межі можна досягти, використовуючи метод Річарда Хеммінга. В коді Хеммінга до речі, що складається з m бітів, додається r біт парності, при цьому утворюється слово довжиною m+r бітів. Біти нумеруються з одиниці (а не з нуля), причому першим вважається крайній лівий. Всі біти, номери яких – ступеня двійки, є бітами парності; інші використовуються для даних. Наприклад, до 16-бітного слова потрібно додати 5 біт парності. Біти з номерами 1, 2, 4, 8 та 16 – біти парності, а всі інші - біти даних. Всього слово містить 21 біт (16 біт даних і 5 біт парності). У розглянутому прикладі будемо використовувати позитивну парність (довільний вибір). Кожен біт парності перевіряє певні бітові позиції. Загальне число бітів зі значенням 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.

 

Біт

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

 

Рис.1.6 — Схема розміщення бітів парності

 

У загальному випадку біт b перевіряється бітами b1, b2,..., bj, такими що b1+b2+...+bj=b.

Наприклад, біт 5 перевіряється бітами 1 і 4, оскільки 1+4=5. Біт 15 перевіряється бітами 1,2,4 і 8, оскільки 1+2+4+8=15 і т. д.

На рис. 1.10 показано побудова коду Хеммінга для 16-бітного слова

 

 

Відповідним 21-бітним кодованими словом є

 

₀₀1₀111₀0000101₁01110

 

Щоб побачити, як відбувається виправлення помилок, розглянемо, що станеться, якщо біт 5 змінить значення через різкий стрибок напруги на лінії електропередачі.

У результаті замість кодованого слова

 

₀₀1₀ 1 11₀0000101₁01110 вийде ₀₀1₀ 0 11₀0000101₁01110

 

Будуть перевірені 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 неправильний (біти 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.7 — Схема розміщення коду з помилкою

 

Біт

 

Рис.1.8 — Схема перевірки бітів парності

 

●

◌

●

◌

●

●

◌

●

●

◌

 

Рис.1.9 — Схема пошуку та виправлення помилок

 

Загальна кількість одиниць в бітах 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.10 – Побудова коду Хеммінга для слова 1111000010101110 за допомогою додавання 5 контрольних розрядів до бітів даних

 

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

Код Ріда - Соломона

 

Код Ріда-Соломона дозволяє скорегувати одну помилку в одному блоці даних. При його використанні до кожного блоку інформації додаються додаткові два елементи X і Y, значення яких знаходяться виходячи з умов:

для трьох одиниць інформації (байт):

байт1 + байт2 + байт3 + X + Y = 0

байт1 + 2 * байт2 + 3 * байт3 + 4 * X + 5 * Y = 0

для розрахунку конкретних значень X і Y для кодування трьох байт:

Y = 3 * байт1 + 2 * байт2 + байт3Х = – 4 * байт1 – 3 * байт2 – 2 * байт3

Тепер для з'ясування помилки і її корекції застосовуємо такі розрахунки:

Значення_помилки = байт1 + байт2 + байт3 + X + Y

так як раніше (до виникнення помилки) ця сума дорівнювала 0, то тепер вона дорівнює безпосередньо значенням помилки, яке досить просто відняти з недоброякісного байта. У разі якщо блок прийнятий безпомилково, то Значення_помилки = 0. Тепер знайдемо байт який треба виправляти:

N = байт1 + 2 * байт2 + 3 * байт3 + 4 * X + 5 * Y

Номер_помилкового_байта = N / Значення_помилки

При реалізації цього в реальний алгоритм необхідно обов'язково здійснювати перевірку на те чи існує помилка в блоці чи ні, тобто Значення_помилки = 0 чи ні, інакше отримуємо ділення на нуль.

Якщо необхідно захистити кодом Ріда-Соломона блок даних більше 3х байт, то формули розрахунку коригувальних значень лише трохи змінюються (для 16 байт):

Y = 16 * байт1 + 15 * байт2 + 14 * байт3 +... + байт16Х = – 17 * байт1 – 16 * *байт2 – 15 * байт3 –... – 2 * байт16

Значення_помилки = байт1 + байт2 + байт3 +... + X + YN = байт1 + 2 * байт2 + 3 * байт3 +... + 16 * байт16 + 17 * X * Y + 18

Даним кодом незручно захищати блоки інформації менше 4 байт, так як довжина контрольних параметрів X і Y повинна бути як мінімум 4 байти, 2 байти (DW) для X та 2 байти Y, тобто виходить, що до блоку даних з 4 байт буде доданий коригувальний блок з 4 байт.

Але що робити, якщо виникло дві або більше помилок у блоці? Як одна з ознак виникнення двох помилок можна вважати отримання як номер_помилкового_байта дробного числа, наприклад якщо у блоці з нулів зустрінеться 2 одиниці (дві помилки), у третьому і четвертому байтах, то Номер_помилкового_байта = 3.5 але якщо 4 одиниці, відповідно до 3, 4 і 5 байтах то Номер_помилкового_байта = 4.

 

СПЕЦІАЛЬНА ЧАСТИНА

Для візуалізації процесу завадостійкого кодування слід розробити пристрій, який допоможе зрозуміти принцип роботи методу Хеммінга. Кодер - декодер будемо розробляти на основі ІМС К555ВЖ1.