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

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

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

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

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

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

.

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

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

К=2⁶+2²+2¹+2⁰=71₁₀.

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

Таблиця 31

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

Наприклад: 47₁₆=0100 0111₂; 001 000 111₂=107₈.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

біта.

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

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

~ ~ ~ ~ ~

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

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

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

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

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

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

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

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

Таблиця 32

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

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

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

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

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

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

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

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

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

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

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

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