Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Способи перетворювання кодів





Перетворення цілих чисел з однієї системи числення з основою в іншу систему числення з основою М можна робити наступними способами.

1-й спосіб. Ділення числа на Мза допомогою арифметики з основою . Цифрами числа в системі числення з основою Мбудуть залишки від ділення. Зручно користуватися цим способом при переведенні з десятквої системи числення (m=10), тому, що використовується десяткова арифметика.

Наприклад: К=7110; 10®8.

71/8 = 8 залишок 7 = ао; 8/8 = 1 залишок 0 = а1; 1/8=0 залишок 1 = а2 . ® К=1078.

2-й спосіб. Множення цифр числа К на ступені за допомогою арифметики основи М, тобто обчислення значення багаточлена:

.

Зручно користуватися при переведенні в десяткову систему числення з інших систем (використовується десяткова арифметика).

Наприклад: К=10001112; 2®10.

К=26+22+21+20=7110.

3-й спосіб. Легко перетворювати числа із системи числення з основою у систему числення з основою М=2Р і навпаки. (Зрозуміло, якщо Р=3, то цевісімкова система числення; якщо Р=4, то цешістнадцяткова система числення. Вони використовуються при опрацюванні даних на ЕОМ.) Для цього потрібно запам’ятати таблиці двійкового запису вісімкових і шістнадцяткових цифр (табл.31).

Таблиця 31

цифра двійковий запис цифра двійковий запис
0 000 1000
0 001 1001
0 010 A(10) 1010
0 011 B(11) 1011
0 100 C(12) 1100
0 101 D(13) 1101
0 110 E(14) 1110
0 111 F(15) 1111

Для перетворення необхідно об’єднати відповідним чином розряди двійкового числа.

Наприклад: 4716=0100 01112; 001 000 1112=1078.

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



Класифікація (двійкових) кодів

Коди діляться за кількістю застосованих кодових комбінацій на ненадлишкові (коли ) й надлишкові (коли < ) . Тут – кількість застосованих кодових комбінацій.

Ненадлишкові коди

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

Ненадлишкові коди бувають рівномірні і нерівномірні.

У рівномірних кодах усі кодові комбінації мають однакову довжину і тому їх не потрібно розмежовувати (відокремлювати одну кодову комбінацію від іншої).

Прикладом може бути телеграфний код, за допомогою якого передають 32 символи російського алфавіту. Код має основу , , біт.

Код із 5 двійкових символів (0,1). Усього з урахуванням цифр і знаків необхідно передавати 54 символи, тому вводять регістрові кодові комбінації, що настроюють приймач на прийом букв або цифр.

У комп’ютерних мережах використовується восьмирозрядний двійковий код ( біт, ). Однак вже відчутна нестача кодових слів для кодування символів у ‑розрядних ЕОМ.

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

Для розв’язання проблеми запропоновано запровадити -бітовий код, спроможний закодувати символів, але поки ще не реалізований.

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

Наприклад, для передачі десяткових цифр потрібний -бітовий рівномірний код: . Тоді як ентропія десяткової цифри не біта, а

біта.

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

Як приклад нерівномірного коду розглянемо код Хаффмена для кодування десяткових цифр

~ ~ ~ ~ ~

~ ~ ~ ~ ~ .

У середньому для запису кодом Хаффмена однієї десяткової цифри потрібно

біта

це майже дорівнює ентропії десяткової цифри біта.

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

Наприклад, для коду Хаффмена: виділяють два старших біта; якщо це « » – то це тетрада (у кодовому слові біта), інакше – це тріада. В такому вигляді цифри передаються каналами зв’язку. Після передачі вже на приймачі в тріадах доповнюють старший біт, а тетради спеціальним чином також перетворюють у двійковий код.

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

Надлишкові коди

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

Помилка виявлена. І тут постає питання: чи можливо її виправити?

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

У залежності від відповіді на це питання надлишкові коди поділяють на коди з виявленням помилок і коди з виправленням помилок.

5.6.2.1. Коди з виявленням помилок

Найпростіший метод виявлення помилок – це перевірка на парність (непарність) суми символів у кодовому слові.

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

Таблиця 32

Кодове слово Число одиниць Кодове слово Число одиниць
0000 1 0101 1
0001 0 0110 1
0010 0 0111 0
0011 1 1000 0
0100 0 1001 1

Загальна кількість кодових слів , а використовується тільки ( < ).

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

5.6.2.2. Коди з виправленням помилок

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

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

Наприклад, повідомлення передають -бітовим кодом із кількістю дозволених кодових комбінацій (А1=010, А2=101). Загальна кількість кодових комбінацій , кількість заборонених кодових комбінацій, які виправляються, .

При поодинокій помилці в А1 (тобто із перекручуванням одного біта) на приймачі може бути отримана одна з таких заборонених кодових комбінацій:{110, 000, 011}. Їм відповідає дозволена кодова комбінація 010. В усіх цих випадках буде правильний прийом.

Відповідно при поодинокій помилці в А2 (один біт перемінить значення на протилежне), маємо іншу підмножину заборонених кодових комбінацій: {001, 111, 100}, їм відповідає дозволена кодова комбінація 101.

Таким чином, якщо передається {110, 000, 011, 010} – читається як 010, якщо {001, 111, 100, 101} – читається як 101. Тобто поодинокі помилки не тільки виявляються, але і виправляються.

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









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.