Аналіз способів кодування інформації

Пояснювальна записка до дипломної роботи

на тему: Розробка пристрою кодування-декодування методом Хеммінга

 

 

Виконав: ст. гр. 5-СКС Грейман О.Л.

Керівник роботи к.т.н. Білецький О.С.

Консультанти:

Охорона праці асистент Кушнір І.П.

Нормоконтролер доцент Сергєєва О.В.

Завідувач кафедри с.н.с.,д.т.н.Чумаков Л.Д.

 

 

Дніпропетровськ

2012

ЗМІСТ

ВСТУП..........................................................................................................................3

1. РОЗДІЛ 1. Загальна частина.......................................................................5

1.1. Аналіз способів кодування інформації..............................................................5

1.2. Перевірка парності............................................................................................16

1.3. Код CRC.............................................................................................................18

1.3.1. Вимоги складності...........................................................................................19

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

1.4. Код Хеммінга.....................................................................................................31

1.5. Код Ріда-Соломона............................................................................................38

2. РОЗДІЛ 2. Спеціальна частина................................................................40

2.1 Розробка пристрою кодування інформації методом Хеммінга....................40

2.2 Розробка пристрою декодування інформації методом Хеммінга.................43

2.3 Реалізація кодера - декодера на базі ІМС К555ВЖ1......................................47

2.3.1 Цоколевка ІМС К555ВЖ1 (SN74LS630).......................................................48

2.3.2 Розробка принципової схеми пристрою.......................................................52

2.3.3 Принцип роботи пристрою.............................................................................53

3. РОЗДІЛ 3. Економічна частина...............................................................54

4. РОЗДІЛ 4. Охорона праці та техніки безпеки..................................59

4.1 Потенційно небезпечні та шкідливі виробничі фактори.................................59

4.2 Забезпечення електробезпеки.............................................................................60

4.3 Забезпечення санітарно-гігієнічних вимог до приміщень

навчальних лабораторій......................................................................................62

4.4 Протипожежний захист.......................................................................................64

ВИСНОВОК...............................................................................................................68

СПИСОК ВИКОРИСТАННОЇ ЛІТЕРАТУРИ........................................................69

Вступ

Характерною рисою науково-технічного прогресу, що визначає потужний подальший підйом суспільного виробництва, є широке впровадження електроніки у всі галузі народного господарства. Стрімкий розвиток промисловості і технологій, визначив подальший розвиток науки на декілька поколінь вперед. Одним з найбільш пріоритетних напрямків науки є мікроелектроніка, яка дозволила досягти високих технологій, які, у свою чергу, знайшли широке застосування як в промисловості, так і в науковій сфері. Стик цих двох сфер сформував найбільший винахід сучасності - електронний цифровий комп'ютер.

Парк комп'ютерів різноманітного призначення зростає стрімкими темпами. В даний час персональний комп'ютер є невід'ємною частиною будь-якого підприємства, навчальних закладів, обчислювальних центрів, та інших установ. З кожним днем зростають обсяги переданої та прийнятої інформації. У зв'язку з цим стає особливо актуальною проблема збереження цілісності переданої та оброблюваної інформації. Пам'ять комп'ютера час від часу може породжувати помилки через сплески напруги на лінії електропередач та з інших причин. Щоб боротися з помилками різного роду, які виникають від час передачі інформації, були розроблені спеціальні способи кодування інформації, що дозволяють виявити і виправити можливі помилки. Існує велика кількість видів завадостійкого кодування і деякі з них настільки складні, що вимагають створення спеціального математичного апарату, інші ж, навпаки, досить прості і зрозумілі. Ефективність різних методів кодування істотно відрізняється і вивчення методів кодування часто стає проблемою через зайву математизованість матеріалу і недостатню наочність. Однак, можливо самостійне виготовлення простого електрифікованого пристрою, який не призведе до значних матеріальних витрат. Виготовлення і використання електрифікованого навчального пристрою дозволить підвищити наочність роботи стендів кодування - декодування і, як наслідок, якість засвоєння матеріалу студентами, що свідчить про актуальність обраної теми.

Метою дипломного проекту є розробка відносно недорого електрифікованого стенду "Пристрій кодування - декодування методом Хеммінга". В ході написання дипломного проекту використовувалися наступні методи: дослідження проблеми, аналіз можливих шляхів вирішення, проектування й модернізація стенду.

 

ЗАГАЛЬНА ЧАСТИНА

Аналіз способів кодування інформації

Історія кодування, що контролює помилки, почалася в 1948 р. публікацією відомої статті Клода Шеннона. Який показав, що з кожним каналом зв’язку пов'язано число С, що є пропускною спроможністю каналу та вимірюється у бітах на секунду (бодах). Пропускна спроможність має наступне значення. Якщо необхідна швидкість передачі інформації R, в залежності від системи зв'язку, менша на С, то використовуючи коди, що контролюють помилки, для цього каналу можна побудувати таку систему зв'язку, в якій ймовірність помилки на виході буде дуже мала. Основний зсув стався, коли Боуз і Рой-Чоудхурі і Хоквингем знайшли великий клас кодів, що виправляють кратні помилки (коди БЧХ), а Рід і Соломон знайшли пов'язаний з кодами БЧХ клас кодів для недвійкових каналів. Хоча ці коди залишаються серед найбільш важливих класів кодів, загальна теорія блокових кодів, контролюючих помилки, з тих часів успішно розвивалася.

Код - форма подання повідомлення, що не залежить від його фізичної суті. Це відрізняє код від сигналу, який визначає фізичне подання повідомлення у системі зв'язку. На практиці часто пов'язують абстрактну форму коду з фізичними сигналами, називаючи код частотним, тимчасовим, фазовим, амплітудним. Код зображують сукупністю символів. Перешкодостійкий код дозволяє виявляти або виправляти помилки в сукупності кодових символів. Якщо повідомлення мають внутрішні кореляційні зв'язки, тобто якщо одне повідомлення деяким чином залежить від іншого, як це зазвичай буває при передачі текстів на природних мовах, то перешкодостійкість будь-якого коду може бути підвищена за рахунок статистичних зв'язків між повідомленнями. Якщо ці зв'язку слабкі, або невідомі, або їх не можна використовувати для підвищення перешкодостійкості, то в цьому випадку форма подання повідомлення повинна бути надмірною; зокрема, кількість символів в коді повідомлення збільшують, а між кодовими символами вводять штучні кореляційні зв'язку. Тому в деяких випадках перешкодостійкі коди називають надмірними. Введення надмірності в код дозволяє крім виявлення і виправлення помилок підвищити енергетичну ефективність лінії зв'язку, звузити частотний спектр переданого сигналу, скоротити час входження в зв'язок шляхом підвищення перешкодозахищеності тракту синхронізації, поліпшити кореляційні властивості сигналів, простими засобами реалізувати рознесений прийом. Вид перешкодостійкого коду залежить від структури системи зв'язку, узагальнена схема якої наведена на рис. 1.1. Розглядаємо системи зв'язку, які передають тільки дискретні повідомлення. У сучасних системах передачі дискретних повідомлень останні надходять на вхід системи, як правило, від декількох джерел. Навіть якщо зовнішнє джерело одне, сама система зв'язку містить джерело сигналів службової зв'язку, телекерування і телесигналізації (ТК-ТС). Швидкість надходження повідомлень від різних джерел інформації (ДІ) може бути як однаковою, так і різною, синхронною з власною тактовою частотою апаратури зв'язку або асинхронної з нею. Блок ущільнення (БУ) об'єднує повідомлення, що надходять від різних джерел, в єдину послідовність, як правило, двійкових символів з тактовою частотою, що відповідає швидкості передачі системи зв'язку.

 

Рис.1.1 — Схема системи зв’язку

ДІ — джерело інформації;

БУ — блок ущільнення повідомлень;

КДЗ, КДВ — кодери зовнішній, внутрішній;

ПРЗ, ПРВ — перемежителі зовнішній, внутрішній;

М — модулятор;

ПД — передавач;

ЛЗ — лінія зв'язку;

ПР — приймач;

Д — демодулятор;

АЦП — аналого-цифровий перетворювач;

БДС, БПС, БЛС — блоки додетекторного, післядетекторного, логічного складання;

ДПЗ, ДПВ — деперемежителі зовнішній, внутрішній;

ДКЗ, ДКВ — декодер зовнішній, внутрішній;

БР — блок розущільнення повідомлень;

ОІ — одержувач інформації;

 

Якщо швидкості надходження повідомлень від джерел асинхронні по відношенню до власної тактовій частоті системи зв'язку, БУ здійснює асинхронне введення повідомлень. Для того щоб при тимчасовому ущільненні розрізнити повідомлення на стороні прийому, БУ формує маркер, що позначає місце першого джерела в загальному цифровому потоці. Маркер періодично повторюється, утворюючи сигнал циклової синхронізації. Кодер вводить надмірність у передаваємий потік двійкових символів, причому кодування повідомлень в залежності від необхідного ступеня підвищення завадостійкості може виконуватися поетапно та з залученням різних кодерів. Перший після БУ кодер називають зовнішнім (КДЗ), останній - внутрішнім (КДВ). Сформований кодером потік символів надходить в перемежитель (ПРВ, ПРЗ). У багатьох випадках помилка в одному символі коду тягне за собою помилки і в інших суміжних з ним символах тої ж послідовності, викликаючи появу пакету помилок на вході декодера, що виправляє помилки. Якщо код розрахований на виправлення m помилок на інтервалі з n суміжних символів, а пакет помилок викликає більше ніж m помилкових символів, помилка декодером не буде виправлена. Перемежитель розносить в часі суміжні символи вихідної кодової послідовності більш ніж на n символів. При деперемежуванні на стороні прийому рознесені символи знову збирають разом; одночасно помилку в пакеті будуть рознесені деперемежителем в часі більш ніж на n символів, і відповідний деперемежителю декодер такі рознесені помилки зможе виправити. Перемежена послідовність кодованих символів надходить у загальному випадку в кілька гілок рознесення, кожна з яких містить модулятор, передавач, лінію зв'язку і приймач. У системах з лініями радіозв'язку для боротьби з завмираннями і вузькополосними перешкодами, чинними в частині частотного діапазону, застосовують програмну (псевдовипадкову) перебудову робочих частот (ППРЧ), відповідні пристрої входять до складу передавача і приймача.

Складання сигналів в рознесених гілках на стороні прийому може здійснюватися як на вході демодулятора (до детекторне складання), так і на його виході (після детекторне складання). Зокрема, якщо сигнали в гілках некогерентні, після детекторне складання називають квадратичним. Порівняно нещодавно в системах зв'язку з кодованими сигналами стали застосовувати логічне об'єднання гілок рознесення, що реалізує після детекторний автовибір гілки з найменшою кількістю помилок. Демодулятор (Д) проводить оптимальну обробку елемента сигналу, що закінчується зазвичай інтегруванням зі скиданням інтегратора в певний тактовий момент часу. Тим самим демодулятор дискретизує в часі суміш огинаючого сигналу з шумом. Формування тактових імпульсів здійснюють пристрої тактової синхронізації, що входять до складу демодулятора. Аналого-цифровий перетворювач (АЦП) на виході демодулятора дискретизує (квантує) суміш огинаючого сигналу з шумом за рівнем. При квантуванні на два рівня декодується двійковий сигнал. Максимальне число рівнів квантування, як правило, не перевищує 16. Зазвичай кількість рівнів дорівнює 2, 4, 8 або 16. Декодер, що працює з двійковим сигналом, називають жорстким, з недвійковим - м'яким. Для роботи декодера необхідні специфічні (групові) тактові імпульси, що формуються в тракті групової синхронізації, що входить до складу декодера. Призначення декодера полягає у зменшенні кількості помилок у повідомленнях, які видаються системою зв'язку, шляхом використання надмірності, закладеної в символьний потік кодером. Частина системи зв'язку, що включає лінію (радіо- або дротову), називається каналом. Частина системи від виходу модулятора до входу АЦП утворює канал передачі-прийому сигналу, безперервного за рівнем (але дискретним за часу). Частина системи від виходу модулятора до виходу АЦП утворює канал з вхідним сигналом, безперервним за рівнем і часом, та з вихідним дискретним сигналом. Від входу модулятора до виходу АЦП маємо дискретний (за часом і рівнем) канал. У двонапрямленій системі зв'язку зазвичай створюють канал зворотного зв'язку, за яким здійснюють управління роботою системи.

Схема на рис. 1.1 може змінити свій вигляд залежно від конкретної реалізації системи зв'язку. В каналах діють викривлені сигнали, шуми, перешкоди, які в дискретному каналі проявляються у вигляді переходу одного значення символу в інше - помилкове (подія, що складається в появі помилки) або незайняте (подія, яку називають стиранням). Залежно від характеру помилок розрізняють дискретні канали: симетричний (всі помилкові значення символів рівноймовірні), асиметричний (деякі помилкові значення символів володіють більшою ймовірністю), без пам'яті (викривлення символу статистично не залежить від викривлення іншого вихідного символу), з пам'яттю (викривлення символу вихідної послідовності статистично залежить від викривлення іншого символу тої ж послідовності), з стиранням (поряд з помилками мають місце стирання символів).

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

Рис. 1.2 — Класифікація завадостійких кодів

 

До теперішнього часу розроблено багато різних завадостійких кодів, що відрізняються один від одного основою, відстанню, надлишковістю, структурою, функціональним призначенням, енергетичною ефективністю, кореляційними властивостями, алгоритмами кодування і декодування, формою частотного спектру. На рис 1.2 наведено типи кодів, що розрізняються за особливостями структури, функціональним призначенням, фізичним властивостям коду як сигналу. Найбільш важливий підклас безперервних кодів утворюють згортаючи коди, що відрізняються від інших безперервних кодів методом побудови і більш широкою областю застосування. У загальному випадку чим довше код при фіксованій надмірності, тим більше відстань і тим вище завадостійкість коду. Однак довгі коди складно реалізуються. Складені коди дають компромісне рішення задачі, з них основне значення мають каскадні коди і коди добутку. Як правило, каскадний код складається з двох ступенів (каскадів): внутрішнього і зовнішнього. По лінії зв'язку сигнали передають внутрішнім кодом n_вн, символьні слова якого є символами зовнішнього коду довжини n_зов. Основа зовнішнього коду доповнює q_зов^k. Коди добутку будують у вигляді матриці, в якій рядки суть слова одного коду, а стовпці – того або іншого коду. При формуванні каскадного коду вхідну інформаційну послідовність символів розбивають на блоки по k_вн символів у кожному, кожен блок зіставляють з інформаційним символом зовнішнього коду з алфавіту, який містить q_зов^k значень символів. Потім k_зов інформаційних символів зовнішнього коду перетворять в блоки з n_зов символів зовнішнього коду і, нарешті, блоки з k_вн інформаційних символів внутрішнього коду перетворять в блоки з n_вн символів внутрішнього коду. Можливі різні варіанти: зовнішній і внутрішній коди - блокові, зовнішній блочний – внутрішній згортаючий, зовнішній згортаючий – внутрішній блочний, зовнішній і внутрішній згортаючи.

Один з найбільш поширених методів формування коду добутку полягає в послідовному записі по k₁ символів вхідної інформаційної послідовності в k₂ рядків матриці (наприклад, в комірки пам'яті ОЗП), додавання надлишкових символів по n₁-k₁ в кожен рядок і по n₂-k₂ в кожен стовпчик, після чого в послідовність символів коду зчитують по рядках або стовпцях з матриці. Фізичним аналогом коду добутку є, зокрема, частотно-часовий код, в якому рядки розташовуються уздовж вісі часу, а стовпці – уздовж вісі частот.

Параметри складених кодів: каскадних – n=п_зовп_вн, k= k_зовk_вн, d=d_зовd_вн; добутку – n=n₁n₂, k=k₁k₂, d=d₁d₂. Похідні коди будують на основі деякого первинного коду, до якого або додають символи, збільшуючи відстань (розширений код), або скорочують частину інформаційних символів без зміни відстані (скорочений код), або викидають (виколюють) деякі символи (виколотий, або перфорований код). Код Хеммінга дає приклад процедури розширення, яка збільшує відстань коду з 3 до 4. Необхідність у виколюванні виникає в результаті побудови на основі початкового коду іншого, менш потужного, більш короткого коду з тож ж відстанню. При більш широкому трактуванні терміну "похідний код" до цього класу можна віднести всі коди, отримані з первинного додаванням або вилученням символів і слів.

Формально поділ кодів на двійкові і недвійкові носить штучний характер; за аналогією слід виділяти трійкові, четвіркові та інші коди більшої основи. Виправдовується такий розподіл ускладненням алгоритмів побудови, кодування та декодування недвійкових кодів. При інших рівних умовах бажано, щоб інформаційні та надмірні символи розташовувалися окремо. У систематичних кодах ця умова виконується. У циклічних кодах кожне слово містить всі свої циклічні перестановки. Усі n циклічних перестановок (слова довжини n) утворюють цикл. У квазіциклічних кодах цикл утворюється на числі символів n-1 або, рідше, n-2. Циклічні коди важливі як з точки зору математичного опису, так і для побудови та реалізації коду.

Помилки в каналах зв'язку мають різний розподіл, однак для вибору завадостійкого коду доцільно розділити всі можливі конфігурації помилок на незалежні (некорельовані) та пакети (корельовані помилки). На практиці доводиться враховувати якість інтервалів між пакетами: вони можуть бути вільними від помилок або ж містити випадкові незалежні помилки. Під кореляційними мають на увазі коди, що володіють хорошими кореляційними властивостями, важливими при передачі сигналів входження в зв'язок, для підвищення захищеності від деяких видів перешкод, вилучення сигналів з інтенсивних шумів, забезпечення багатостанційного доступу, побудови асинхронно-адресних систем зв'язку. Кореляційні коди включають в себе пари протилежних сигналів з гарною функцією автокореляції (метод внутрішньоімпульсної модуляції), імпульсно-інтервальні коди, які мають на фіксованому інтервалі часу постійну для всіх слів коду кількість імпульсів з неперетинними (при будь-якому взаємному зсуву слів у часі) значеннями інтервалів між імпульсами, ансамблі сигналів з хорошими взаємнокореляційними властивостями.

Особливий клас утворюють частотно-компактні коди, призначені для зосередження енергії сигналу в можливо більш вузькій смузі частот. Така загальна постановка завдання розуміється в різних системах зв'язку по-різному: в кабельних лініях і лінійних трактах, що містять смугообмежуючи фільтри з крутими фронтами, необхідно основну енергію сигналу "відсунути" від крайніх частот до центру смуги пропускання з метою зменшення міжсимвольних викривлень; в мережах радіозв'язку з жорсткими обмеженнями щодо електромагнітної сумісності радіозасобів від коду потрібно значно (на десятки децибел) зменшити рівень позасмугових випромінювань. Побудова кодування і декодування частотно-компактних кодів істотно залежать від методу модуляції. Арифметичні коди служать для боротьби з помилками при виконанні арифметичних операцій в процесорі ЕОМ.

Також виділені ще два типи кодів: блокові та деревоподібні. Визначаюча різниця між кодерами для кодів цих двох типів полягає в наявності або відсутності пам'яті. Кодер для блокового коду є пристроєм без пам'яті, що відображає послідовності з k вхідних символів у послідовності з n вихідних символів. Термін "без пам'яті" вказує, що кожен блок з n символів залежить тільки від відповідного блоку з k символів і не залежить від інших блоків. Це не означає, що кодер не містить елементів пам'яті. Важливими параметрами блокового коду є n, k, R=k/n і d_min. На практиці значення k лежить між 3 і кількома сотнями, a R =1/4...7/8. Значення, які лежать поза цих меж, є можливими, але часто призводять до деяких практичних труднощів. Вхідні і вихідні послідовності зазвичай складаються з двійкових символів, але іноді можуть складатися з елементів деякого алфавіту більшого об'єму. Кодер для деревоподібного коду є пристроєм з пам'яттю, в який надходять набори з m двійкових вхідних символів, а на виході з'являються набори з n двійкових вихідних символів. Кожен набір n вихідних символів залежить від поточного вхідного набору і від v попередніх вхідних символів. Таким чином, пам'ять кодера повинна містити v+m вхідних символів. Параметр v+m часто називають довжиною кодового обмеження даного коду і позначають k=v+m (не слід плутати з параметром k для блокового коду). Довжиною кодового обмеження будемо називати величину v. Типові значення параметрів деревоподібних кодів такі: m, n =1...8, R =1/4... 7/8, v =2...60.

При іншому підході коди можна розділити на лінійні і нелінійні. Лінійні коди утворюють векторний простір і володіють наступною важливою властивістю: два кодових слова можна скласти, використовуючи відповідне визначення суми, і отримати третє кодове слово. У разі звичайних двійкових кодів ця операція є символьним складанням двох кодових слів за модулем 2 (тобто. 1+1=0, 1+0=1, 0+0=0). Ця властивість призводить до двох важливих наслідків. Перша з них полягає в тому, що лінійність істотно спрощує процедури кодування і декодування, дозволяючи висловити кожне кодове слово у вигляді "лінійної" комбінації невеликого числа виділених кодових слів, так званих базисних векторів. Друга властивість полягає в тому, що лінійність істотно спрощує завдання обчислення параметрів коду, оскільки відстань між двома кодовими словами при цьому дорівнює відстані між кодовим словом, що складається цілком з нулів, і деяким іншим кодовим словом. Таким чином, при обчисленні параметрів лінійного коду досить розглянути, що відбувається при передачі кодового слова, що складається цілком з нулів. Обчислення параметрів спрощується ще й тому, що відстань Хеммінга між даними кодовим словом і нульовим кодовим словом дорівнює числу ненульових елементів даного кодового слова. Це число часто називають вагою Хеммінга цього слова, і список, що містить число кодових слів кожної ваги, можна використовувати для обчислення характеристик коду за допомогою адитивного ліміту. Такий список називають спектром коду. Лінійні коди відрізняються від нелінійних замкнутістю кодової множини щодо деякого лінійного оператора, наприклад додавання і множення слів коду, розглянутих як вектори простору, що складаються з кодових слів – векторів. Лінійність коду спрощує його побудову та реалізацію. При великій довжині практично можуть бути використані тільки лінійні коди. Разом з тим часто нелінійні коди володіють кращими параметрами порівняно з лінійними. Для відносно коротких кодів складність побудови та реалізації лінійних і нелінійних кодів приблизно однакова. Як лінійні, так і нелінійні коди утворюють великі класи, які містять багато різних конкретних видів завадостійких кодів. Серед лінійних блочних найбільше значення мають коди з однією перевіркою на парність, M-коди (симплексні), ортогональні, біортогональні, Хеммінга, Боуза-Чоудхурі-Хоквінгема, Голея, квадратично-вирахувальні (KB), Ріда-Соломона. До нелінійних відносять коди з контрольною сумою, інверсні, Нордстрома-Робінсона (HP), з постійною вагою, перестановочні з повторенням і без повторення символів (повні коди ортогональних таблиць, проектних груп, груп Матьє та інших груп перестановок). Майже всі схеми кодування, що застосовуються на практиці, засновані на лінійних кодах. Подвійні лінійні блокові коди часто називають груповими кодами, оскільки кодові слова утворюють математичну структуру, звану групою. Лінійні деревовидні коди зазвичай називають згортаючими кодами, оскільки операцію кодування можна розглядати як окрему згортку вхідної послідовності з імпульсним відгуком кодера.

Нарешті, коди можна розбити на коди, що виправляють випадкові помилки, і коди, що виправляють пакети помилок. В основному будемо мати справу з кодами, призначеними для усунення випадкових або незалежних, помилок. Для пакетів виправлення помилок було створено багато кодів, які мають хороші параметри. Однак при наявності пакетів помилок часто виявляється більш вигідним використовувати коди, що виправляють випадкові помилки, разом з пристроєм перемеження відновлення. Такий підхід включає в себе процедуру перемішування порядку символів в закодованій послідовності перед передачею та відновленням вихідного порядку символів після прийому з тим, щоб рандомізувати помилки, об'єднані в пакети.

 

Перевірка парності

 

Контроль парності або корекція помилок (ECC – код виправлення помилок) використовується в основному тільки в найбільш важливих комп'ютерних системах, де неприпустима навіть одна помилка за кілька десятиліть. Перевірка парності – досить простий метод виявлення помилок пам'яті, без можливості відновлення. Кожен байт даних пов'язаний з одним бітом парності або так званим паритетним бітом. Цей біт встановлюється під час запису, і потім розраховується і порівнюється під час читання. Зміна стану цього біта говорить про цю помилку. Цей метод обмежений визначенням зміни стану одиночного біта у байті. У разі зміни стану двох бітів, можлива ситуація, коли обчислення паритетного біта співпаде з записаним. У цьому випадку система не визначить помилку, і відбудеться екстрена зупинка системи. Так як приблизно 90% всіх нерегулярних помилок відбувається саме з одиночним розрядом, перевірки парності буває достатньо для більшості ситуацій. На жаль необхідність у додаткових обчисленнях паритетного біта вимагає певних витрат процесорного часу, що дещо знижує продуктивність всієї системи. Більш цікавим методом перевірки помилок роботи пам'яті є так звана корекція помилок (ECC) або код виправлення помилок. Цей метод включає визначення помилки не тільки в одиночному розряді, але і двох, трьох і чотирьох розрядах. ECC може бути реалізований або на модулі пам'яті (ECC - on - Simm, або EOS) або в чіпсеті. Однак модулі EOS зустрічаються вкрай рідко. ECC базується на алгоритмі "хешинга", який працює одночасно з 8 байт (64 біт), і розміщує результат у 8-ми розрядне ECC слово. Під час зчитування результат ECC слова порівнюється з розрахованим, подібно до того, як відбувається в методі перевірки парності. Основна відмінність полягає в тому, що в перевірці кожен біт парності пов'язаний з одним байтом, у той час як ECC слово пов'язана з усіма 8 байтами. Це означає, що розрядні значення для ECC не будуть тими ж, що й індивідуальні біти для перевірки парності для тих же восьми байтів, тому модулі ECC не можуть використовуватися в режимі парності (однак, паритетні модулі, можуть використовуватися в режимі ECC, як описано нижче). ECC модулі можуть використовуватися на не паритетних і на ECC / non-ECC платах. Модуль ECC не може використовуватися в режимі перевірки парності. Причина цього є схемотехнічна реалізація модуля ECC. Він не може встановлювати окремі біти, тому чіпсет не буде записувати правильні дані в ECC слово.

Код CRC

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

 

Повідомлення: 6 4 23

Повідомлення з контрольною сумою: 6 23 4 33

Повідомлення після передачі: 6 27 4 33

 

Як видно, другий байт повідомлення при передачі виявився зміненим з 23 на 27. Приймач може виявити помилку, порівнюючи передану контрольну суму 33 з розрахованої їм самим: 6 + 27 + 4 = 37. Якщо при правильній передачі повідомлення виявиться пошкоджена сама контрольна сума, то таке повідомлення буде неправильно витлумачено, як викривлене. Однак, це не найгірша ситуація. Більш небезпечно, одночасне пошкодження повідомлення та контрольної суми таким чином, що всі повідомлення можна вважати достовірними. На жаль, виключити таку ситуацію неможливо, і краще, чого можна досягти, це знизити ймовірність її появи, збільшуючи кількість інформації в контрольній сумі (наприклад, розширивши її з одного до 2 байт).

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

Вимоги складності

Вище показано, що пошкодження повідомлення може бути виявлено, використовуючи в якості алгоритму контролю просте додавання байтів повідомлення по модулю 256:

 

Повідомлення: 6 23 4

Повідомлення з контрольною сумою: 6 23 4 33

Повідомлення після передачі: 6 27 4 33

Недолік цього алгоритму в тому, що він дуже простий. Якщо відбудеться кілька викривлень, то в 1 випадку з 256 не зможемо їх знайти. Наприклад:

Повідомлення: 6 4 23

Повідомлення з контрольною сумою: 6 23 4 33

Повідомлення після передачі: 8 20 5 33

Для підвищення надійності можна було б змінити розмір регістра з 8-бітного на 16 бітний (тобто підсумувати по модулю 65536 замість модуля 256), що, швидше за все, знизить імовірність помилки з 1/256 до 1/65536. Хоча це і непогана ідея, проте, вона має той недолік, що застосовується формула розрахунку яка не "випадкова" належною мірою – кожен додаваємий байт впливає лише на один байт підсумкового регістра, при цьому ширина самого регістра не має ніякого значення. Наприклад, у другому випадку підсумовуючий регістр міг би мати ширину хоч мегабайт, проте помилка все одно не була виявлена. Проблема може бути вирішена лише заміною простого підсумовування більш складною функцією, щоб кожен новий байт впливав на весь реєстр контрольної суми.

Таким чином, сформульовано дві вимоги для формування надійної контрольної суми:

Ширина. Розмір регістра для обчислень повинен забезпечувати початкову низьку ймовірність помилки (наприклад, 32 байтний регістр забезпечує ймовірність помилки 1/232).

Випадковість. Необхідний такий алгоритм розрахунку, коли кожен новий байт може вплинути на будь-які біти регістра.

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

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

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

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

Припустимо, що повідомлення складається з 2 байт (6, 23), як і в попередньому прикладі. Їх можна розглядати, як шістнадцяткове число 0617h, або як двійкове число 0000 0110 0001 0111. Припустимо, що ширина регістра контрольної суми становить 1 байт, а як дільник використовується 1001, тоді сама контрольна сума дорівнюватиме залишку від ділення 0000 0110 0001 0111 на 1001. Хоча в цій ситуації розподіл може бути виконано з використанням стандартних 32 бітних регістрів, в загальному випадку це не вірно. Тому скористаємося діленням у "стовпчик". Тільки на цей раз, воно буде виконуватися в двійковій системі числення. Ділення у двійковій системі проводиться вирахуванням дільника зі зрушенням вправо, якщо залишок більше нуля.

(6, 23)=0000 0110 0001 0111_BIN = 0617_HEX = 1559_DEC

 

					1024+512+16+4+2+1=1559DEC	128+32+8+4+1=173DEC
					1024	512	256	128	64	32	16	8	4	2	1	128	64	32	16	8	4	2	1
0	6	1	7	→ 0617HEX
																1	0	0	1	9DEC
				–	1	0	0	1	↓	↓	↓	↓	↓	↓	↓	1	0	1	0	1	1	0	1
				=	0	0	1	1	0	0	1	0	1	1	1
					→	1	0	0	1		↓	↓	↓	↓	↓	0
						–	1	0	0	1	1
						=	0	0	1	1	1	0	1	1	1
							→	1	0	0	1		↓	↓	↓	0
								–	1	0	0	1	1
								=	0	1	0	1	1	1	1
									–	1	0	0	1	↓	↓	1
									=	0	0	1	0	1	1
										→	1	0	0	1		0
											–	1	0	0	1	1
											=	0	0	1	0	Залишок від ділення = 2

 

Рис.1.3 — Схема ділення у двійковій системі числення

 

Робимо перевірку:

1559 / 9 = 173 та залишок 2;

0000 0110 0001 0111 / 1001 = 10101101 та залишок 0010;

10101101 = 173;

0010 = 2;

Ділення у двійковій системі числення виконано вірно.

В десятковому вигляді це буде звучати так: "частка від ділення 1559 на 9 дорівнює 173 і 2 в залишку".

Хоча вплив кожного біта вихідного повідомлення на частку не настільки істотний, однак 4 бітний залишок під час обчислень може радикально змінитися, і чим більше байтів є у вихідному повідомленні (у діленому), тим сильніше змінюється кожного разу величина залишку. Ось чому поділ виявляється застосовується там, де звичайне складання працювати відмовляється.

У нашому випадку передача повідомлення разом із 4 бітною контрольною сумою виглядала б (у шістнадцятковому вигляді) наступним чином: 06172, де 0617 - це саме повідомлення, а 2 - контрольна сума. Приймач, отримавши повідомлення, міг би виконати аналогічне поділ і перевірити, дорівнює чи залишок переданому значенню (2).

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

Поліном є дільником CRC алгоритму. Усі CRC алгоритми засновані на поліноміальних обчисленнях, і для будь-якого алгоритму CRC можна вказати, який поліном він використовує.

Замість подання дільника, діленого (повідомлення), частки і залишку у вигляді позитивних цілих чисел можна представити їх у вигляді поліномів з двійковими коефіцієнтами або у вигляді рядка біт, кожен з яких є коефіцієнтом полінома. Наприклад, десяткове число 23 у шістнадцятковій системі числення має вигляд 17, а в двійковому – 10111, що збігається з поліномом:

 

1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0 або, простіше:

x^4 + x^2 + x^1 + x^0

І повідомлення, і дільник можуть бути представлені у вигляді поліномів, з якими, як і раніше можна виконувати будь-які арифметичні дії. Припустимо, що хочемо перемножити, наприклад, 1101 і 1011. Це можна виконати, як множення поліномів:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)

= (x^6 + x^4 + x^3

+ x^5 + x^3 + x^2

+ x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Тепер для отримання правильної відповіді необхідно вказати, що Х дорівнює 2 (двійкова система числення), і виконати перенесення біта від члена 3*x^3.

В результаті отримаємо:

x^7 + x^3 + x^2 + x^1 + x^0

Все це дуже схоже на звичайну арифметику, з тією лише різницею, що основа у нас лише передбачається, а не чітко вказано. Якщо "X" невідомий, то не можемо виконати перенесення. Невідомо, що 3*x^3 – це те ж саме, що і x^4 + x^3, бо не знаємо, що X=2. У поліноміальній арифметиці зв'язки між коефіцієнтами не встановлені, і, тому, коефіцієнти при кожному членові полінома стають строго типізованими – коефіцієнт при x^2 має інший тип, ніж при x^3.

Якщо коефіцієнти кожного члена полінома повністю ізольовані один від одного, то можна працювати з будь-якими видами поліноміальної арифметики, просто змінюючи правила, за якими коефіцієнти працюють. Одна з таких схем для нас надзвичайно цікава, а саме, коли коефіцієнти складаються за модулем 2 без переносу – тобто коефіцієнти можуть мати значення лише 0 або 1, перенесення не враховується. Це називається "поліноміальна арифметика за модулем 2".

 

Повертаючись до попереднього прикладу:

 

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)

= (x^6 + x^4 + x^3

+ x^5 + x^3 + x^2

+ x^3 + x^1 + x^0)

= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

 

За правилами звичайної арифметики, коефіцієнт члена 3*x^3 розподіляється по іншим членам полінома, використовуючи механізм перенесення і припускаючи, що X=2. В "поліноміальній арифметиці за модулем 2" не відомо, чому дорівнює "X", переносів тут не існує, а всі коефіцієнти розраховуються за модулем 2.

В результаті одержуємо:

 

= x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

 

Таким чином, поліноміальна арифметика за модулем 2 – це фактично двійкова арифметика за модулем 2 без урахування переносів. Хоча поліноми мають зручні математичні засоби для аналізу CRC алгоритмів і алгоритмів корекції помилок, для спрощення вони будуть замінені, на безпосередньо арифметичні дії в системі, з якою вони ізоморфні (відносно еквівалентні), а саме в двійковій системі арифметики без переносів.