31300

Системи числення, кодування інформації

Практическая работа

Информатика, кибернетика и программирование

Можна вигадати незлічену кількість способів запису числа цифровими знаками але практично застосована система числення повинна давати змогу: зображувати будьяке число в розглядуваному діапазоні величин; одержувати єдине зображення кожної величини; просто виконувати операції з числами. Розрізняють позиційні і непозиційні системи числення. Непозиційною системою числення називають спосіб зображення чисел коли значення цифри не залежить від її позиції в числі наприклад римський запис числа.

Украинкский

2013-08-28

287.5 KB

20 чел.

ПРАКТИЧНЕ ЗАНЯТТЯ №7

Тема:  Системи числення, кодування інформації

Мета заняття: Навчитися переводити числа в довільну систему числення, ознайомитися з принципами побудови кодів Грея та Хемінга, навчитися переводити числа з ддвійкового коду в циклічний та навпаки, визначати помилки передачі даних за допомогою коду з перевіркою на парність (непарність) та  виправляти їх за допомогою коду Хемінга

1 ТЕОРЕТИЧНІ ВІДОМОСТІ

Під системою числення розуміють сукупність способів і правил для зображення чисел цифровими знаками. Можна вигадати незлічену кількість способів запису числа цифровими знаками, але практично застосована система числення повинна давати змогу: зображувати будь-яке число в розглядуваному діапазоні величин; одержувати єдине зображення кожної величини; просто виконувати операції з числами.

Розрізняють позиційні і непозиційні системи числення. Непозиційною системою числення називають спосіб зображення чисел, коли значення цифри не залежить від її позиції в числі (наприклад, римський запис числа). Непозиційні системи не дістали розповсюдження в цифрових пристроях, оскільки в них дуже складні та громіздкі алгоритми зображення чисел і виконання арифметичних операцій.

У позиційній системі числення кожної цифри залежить від її положення (позиції) в числі. Наприклад, десяткове число 4954 можна зобразити у вигляді суми зважених коефіцієнтів:

.

З цього запису видно, що місце коефіцієнта в числі однозначно визначає показник степеня, до якого треба піднести число 10. У десятковій системі використовують десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Кількість різних цифр , використовуваних у позиційній системі числення, називають її основою. За аналогією з десятковою можна казати про двійкову, трійкову, вісімкову, дванадцяткову та інші системи, назва яких залежить від основи. У двійковій системі числення для запису чисел використовують два символи – 0 і 1, у трійковій – символи 0, 1 та 2. У довільній системі числення з основою  застосовують цифри 0, 1, ..., . Кількість цифр у деякому числі називають його розрядністю.

У загальному випадку довільне число  у позиційній системі числення з основою  можна зобразити у вигляді полінома від основи

,  (7.1)

або

,  (7.2)

де  і  - кількість розрядів відповідно цілої й дробової частин числа.

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

Алгоритм переведення чисел діленням на основу нової системи, який застосовують для цілих чисел, ґрунтується на використанні запису (7.1) за схемою Горнера:

,  (7.3)

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

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

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

.

Тоді в новій системі числення з основою  це число буде зображено у вигляді

.

Переписавши цей вираз за схемою Горнера, одержимо

.  (7.4)

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

За розглянутим алгоритмом зручно переводити лише числа з десяткової системи числення, оскільки множити в довільній системі незвично і важко.

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

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

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

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

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

Послідовність символів деякого алфавіту називають словом у ньому, а кодуванням – перетворення слів початкового алфавіту в слова іншого згідно із заданою системою відповідностей. Унаслідок кодування дістають кодові слова.

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

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

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

Таблиця 7.1

Число

Двійковий код

Код Грея

Число

Двійковий код

Код Грея

0

0000

0000

8

1000

1100

1

0001

0001

9

1001

1101

2

0010

0011

10

1010

1111

3

0011

0010

11

1011

1110

4

0100

0110

12

1100

1010

5

0101

0111

13

1101

1011

6

0110

0101

14

1110

1001

7

0111

0100

15

1111

1000

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

Рис. 7.1 Перетворення двійкового коду числа 9 у код Грея

При зворотному перетворенні старший біт залишають без змін, а інші визначають наступним чином: якщо йому передує парне число одиниць, біт залишають без зміни, в противному випадку – інвертують.

Код Грея широко застосовують у модулях керування та контролю.

Коди з постійною вагою – рівномірні блокові коди з постійною кількістю одиниць у кожній кодовій комбінації. До таких кодів відносяться широко використовувані в телеграфії коди з постійним співвідношенням різнополярних імпульсів, наприклад, міжнародний телеграфний код №3 містить три імпульси струму і чотири – без струму.  Збільшення чи зменшення кількості посилок струму у коді говорить про наявність помилки.

По можливості виявлення і виправлення помилок розрізняють прості (примітивні) і коригувальні коди. У простих кодах помилка в прийомі хоча б одного елемента кодової комбінації приводить до неправильної реєстрації переданого повідомлення. Коригувальні коди дозволяють виявляти і усувати помилки в кодових комбінаціях.

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

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

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

. (7.5)

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

Це пред'являє до  вимогу задоволення нерівності

(7.6)

Відповідно до виразу (7.5), можна записати

. (7.7)

Використовуючи формулу (7.5), записуємо

,

де  – повне число комбінацій коду.

Таким чином, число інформаційних символів коду, що виявляє і коректує одиничну помилку

, (7.8)

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

Для обчислення основних параметрів коду задається кількість або інформаційних символів, або інформаційних комбінацій – . За допомогою формул (7.5) і (7.8) обчислюють  і . Співвідношення між ,  і  для коду Хемінга представлені в таблиці 7.2.

Знаючи основні параметри коригувального коду, визначають, які позиції сигналів будуть робочими, а які контрольними. Практика показала, що номера контрольних символів зручно вибирати за законом , де 0, 1, 2, 3,… -  натуральний ряд чисел. Номера контрольних символів у цьому випадку рівні 1, 2, 4, 8, 16, 32... Потім визначають значення контрольних коефіцієнтів (0 чи 1), керуючись наступним правилом: сума одиниць на перевірочних позиціях повинна бути парною. Якщо ця сума парна – значення контрольного коефіцієнта 0, у противному випадку – 1.

Таблиця 7.2

Співвідношення між кількістю інформаційних і контрольних символів у коді Хемінга

1

2

3

4

5

6

7

8

0

0

1

1

2

3

4

4

1

2

2

3

3

3

3

4

9

10

11

12

13

14

15

16

5

6

7

8

9

10

11

11

4

4

4

4

4

4

4

5

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

Далі виявляють значення перевірочних позицій, виписуючи коефіцієнти за наступним принципом: у першу перевірку входять коефіцієнти, що містять 1 у молодшому розряді, тобто  і т.д.; у другу перевірку – коефіцієнти, що містять 1 у другому розряді, тобто  і т.д.; у третю перевірку – коефіцієнти, що містять 1 у третьому розряді і т.д. Номера перевірочних коефіцієнтів відповідають номерам перевірочних позицій, що дозволяє скласти загальну таблицю перевірок (таблиця 7.3).

Таблиця 7.3

Номера перевірочних позицій коду Хемінга

№ перевірки

Перевірочні позиції

№ контрольного символу

1

2

3

4

1, 3, 5, 7, 11, …

2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 24, …

4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, …

8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, …

1

2

4

8

 

2 КОНТРОЛЬНИЙ ПРИКЛАД

1. Задані десяткові числа А, B, C перевести в зазначені системи числення.

2. Двійковий код чисел A, B, C перевести в код Грея і для перевірки знову з двійковий код.

3. Побудувати для двійкових кодів чисел А, В, С код для передачі з перевіркою на парність. Розрядність коду визначити по більшому, кратному двом числу щодо більшого з А, В і С.

4. Побудувати для двійкового коду числа А код Хемінга:

а) визначити кількість інформаційних розрядів у слові (див. п.3);

б) визначити кількість контрольних груп;

в) визначити значення контрольних розрядів і записати передане слово для А при передачі без помилки і з одною помилкою (на вибір).

А = 23, В = 45, С = 17. Системи числення: 2,5,8,16.

Рішення.

1. Для переводу чисел в системи числення з основами 2 і 5 скористаємося методом порозрядного зважування. Для переводу в системи числення з основами 8 і 16 скористуємося двійковим кодом, об’єднаним  відповідно в тріади і тетради. Отримаємо:

; ; .

; ; .

; ; .

2. Для прямого і зворотного переводу в код Грея двійкових чисел використаємо вище вказані правила (див рис. 7.1 та пояснення до нього). Отримаємо:

; ; .

3. Припустимо, що числа А, В і С передають по одній шині даних. Тоді, з урахуванням того, що найбільше з них містить 6 розрядів, відводимо для контрольного розряду 7-ме місце зліва. Менші слова доповнюємо зліва незначущими нулями. Значення контрольного розряду для кожного випадку визначаємо у відповідності з наведеним вище правилом. Отримаємо:

4. Побудуємо для двійкового коду числа А код Хемінга:

а) кількість значущих інформаційних розрядів в числі А – 5 (див. п.3);

б) кількість контрольних груп дорівнює кількості контрольних розрядів, тобто, у відповідності з (7.5) і (7.6), ;

в) для того, щоб визначити значення контрольних розрядів і записати передане слово для А при передачі без помилки, побудуємо допоміжну карту переводу (див. рис. 7.2). По вертикалі в цій карті виділено контрольні групи, по горизонталі – розряди слова, що передається. Контрольні розряди займають в карті місця 1, 2, 4 і 8, тобто , ,  і . Занесемо число А в карту, як це показано на рис. 7.2, починаючи з крайнього правого розряду.

1

1

0

1

0

0

0

0

0

0

1

0

1

1

1

1

1

0

1

0

0

0

0

0

0

(0)

0

1

1

1

Рис. 7.2 карта для роботи з кодом Хемінга

В невикористані місця для контрольних розрядів занесемо незначущі 0. Далі визначимо значення контрольних розрядів в кожній групі, сумуючи за модулем 2 всі одиниці числа, що співпадають зі знаками карти і доповнюючи суму до парності відповідним значенням в контрольному розряді.

Для першої групи:

- непарне число, тобто контрольний розряд повинен дорівнювати 1.

Для другої групи:

- непарне число, тобто контрольний розряд повинен дорівнювати 1.

Для третьої групи:

- непарне число, тобто контрольний розряд повинен дорівнювати 1.

Для четвертої групи:

- парне число, тобто контрольний розряд повинен дорівнювати 0.

Таким чином, слово, що передається, дорівнює 110100000010111.

В тому випадку, коли слово передається без помилок, згортка з урахуванням контрольних розрядів дасть для кожної групи парне число, тобто нові значення контрольних розрядів  - 0000. Припустимо, що при передачі інформації в одинадцятому розряді замість 1 був отриманий 0 (див. рис. 7.2). визначимо нові значення контрольних розрядів.

Для першої групи:

- непарне число, тобто контрольний розряд повинен дорівнювати 1.

Для другої групи:

- непарне число, тобто контрольний розряд повинен дорівнювати 1.

Для третьої групи:

- парне число, тобто контрольний розряд повинен дорівнювати 0.

Для четвертої групи:

- непарне число, тобто контрольний розряд повинен дорівнювати 1.

Зваживши на те, що четвертий контрольний розряд є старшим, отримаємо код 1011=11, тобто нові значення контрольних розрядів вказують, в якому розряді слова, що передається, допущено помилку.

3 ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

1. Задані десяткові числа А, B, C перевести в зазначені системи числення.

2. Двійковий код чисел A, B, C перевести в код Грея і для перевірки знову з двійковий код.

3. Побудувати для двійкових кодів чисел А, В, С код для передачі з перевіркою на парність. Розрядність коду визначити по більшому, кратному двом числу щодо більшого з А, В і С.

4. Побудувати для двійкового коду числа В код Хемінга:

а) визначити кількість інформаційних розрядів у слові (див. п.3);

б) визначити кількість контрольних груп;

в) визначити значення контрольних розрядів і записати передане слово для В при передачі без помилки і з одною помилкою (на вибір).

а) А = 21, В = 41, С = 13. Системи числення: 2,3,8,16.

б) А = 25, В = 48, С = 11. Системи числення: 2,4,9,16.

4 КОНТРОЛЬНІ  ПИТАННЯ

  1.  Що розуміють під системою числення?
  2.  Назвіть і охарактеризуйте відомі алгоритми для переводу чисел з однієї системи числення до іншої.
  3.  Що називається кодом?
  4.  З якими типами кодів ви знайомі?
  5.  В яких пристроях використовується код Грея?
  6.  Як перевести двійкове число в код Грея і навпаки?
  7.  З якою метою використовується код Хемінга?
  8.  Як визначити необхідну кількість контрольних розрядів при кодуванні за Хемінгом?
  9.  Як побудувати для двійкового коду числа код Хемінга?
  10.  Як за допомогою коду Хемінга визначаються помилки при передаванні інформаційних слів?

80


 

А также другие работы, которые могут Вас заинтересовать

16112. Історія держави і права зарубіжних країн 1.63 MB
  Держава і право Стародавнього Єгипту. Держава і право Стародавньої Греції. Виникнення і розвиток буржуазної держави і права в Англії. Виникнення і розвиток буржуазної держави і права у Німеччині. Держава і право США.
16113. Житлове право України 1.2 MB
  Мічурін Є.О. Сліпченко С.О. Соболев О.В. Житлове право України Науковопрактичний посібник. Харків: Еспада 2004. С.318. У посібнику розглядаються питання житлового права України характеризуються основні засоби здійснення права на житло що передбачені Конституцією Ук
16114. Господарське законодавство 2.72 MB
  Нормативне регулювання господарських відносин ґрунтується на встановлених Конституцією України основних засадах правопорядку у сфері господарювання, про що згадується в Преамбулі Господарського кодексу України, а в ст. 5 Господарського кодексу цьому питанню приділяється спеціальна увага. Зокрема
16115. Державне управління. Навчальний посібник 1.54 MB
  Навчальний посібник «Державне управління» зорієнтований на освітньо-професійні програми підготовки магістрів державної служби та магістрів за спеціальністю «Адміністративний менеджмент». У посібнику розглядаються основи теорії державного управління, система органів державної влади в Україні, їхні функції та повноваження, напрямки реформування організаційних структур державного управління за Концепцією адміністративної реформи в Україні, основи внутрішньої організації та менеджменту державних органів.
16116. Кримінальне право України. Загальна частина. Навчальний посібник 2.05 MB
  У підручнику висвітлюються основні питання Загальної частини кримінального права України, розкривається зміст (у загальних рисах) кримінального законодавства іноземних держав. Розрахований на студентів, аспірантів (адюнктів) та викладачів вищих юридичних навчальних закладів, а також науковців і практичних працівників
16117. Риторика. Навчальний посібник 1.98 MB
  Розглянуто предмет риторики, основний зміст понять і всіх розділів класичної риторики. Висвітлено надбання цієї науки за всю історію її розвитку, які покладено в основу сучасних наук: неориторики, стилістики, поетики, прагматики, теорії комунікації тощо. Посібник містить також дидактичний матеріал та зразки ораторської майстерності.
16118. Державне управління. Навчальний посібник 3.49 MB
  Посібник подає у формі навчального матеріалу основні теоретичні засади науки державного управління. Викладені у ньому основи адміністративно-управлінської науки - історія та теорія державного управління - розглядаються в контексті сучасних досягнень у цій галузі й базуються на практичній управлінській діяльності.
16119. Сучасні правові системи світу. Навчальний посібник 1.79 MB
  Курси порівняльного правознавства у західних університетах є традиційними вже багато років. В юридичних вузах багатьох країн світу викладається навчальний курс Основні правові системи сучасності. Нині існує нагальна потреба в оновленні системи вищої юридичної освіти в Україні, приведення її у відповідність з потребами нашого часу, загальноєвропейськими вимогами.
16120. нститут адміністративної відповідальності, ароблеми розвитку. Навчальний посібник 864.5 KB
  Монографія присвячена одному Із основних інститутів адміністративного права — Інституту адміністративної відповідальності. Розглядається Історія його розвитку та сучасний стан. Основна увага приділяється найбільш актуальним проблемам адміністративної відповідальності, зокрема відповідальності юридичних осіб. її підставам. принципам і функціям. Для науковців, аспірантів і студентів юридичних навчальних закладів.