Теорія кодування. Види кодування. Народження теорії кодування Класифікація методів кодування

«Мета цього курсу – підготувати вас до вашого технічного майбутнього.»

Привіт Хабр. Пам'ятаєте офігенну статтю «Ви та ваша робота» (+219, 2442 в закладки, 394k прочитань)?

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

Це книга не просто про ІТ, це книга про стиль мислення неймовірно крутих людей. «Це не просто заряд позитивного мислення; в ній описані умови, які збільшують шанси зробити велику роботу.

Ми вже переклали 28 (із 30) розділів. І ведемо роботу над виданням «у папері».

Теорія кодування - I

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

Для спрощення проблеми подання інформації розглянемо проблему передачі від точки до точки. Це питання пов'язане з питанням збереження інформації. Проблеми передачі у часі та у просторі ідентичні. На малюнку 10.1 представлено стандартну модель передачі.

Малюнок 10.1

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

Коли наприкінці 1940 років Шеннон створив теорію інформації, вважалося, що вона мала називатися теорією зв'язку, але він наполяг на терміні інформація. Цей термін став постійною причиною як підвищеного інтересу, і постійних розчарувань теорії. Слідчі хотіли будувати цілі «теорії інформації», вони вироджувались у теорії набору символів. Повертаючись до моделі передачі, ми маємо джерело даних, які необхідно закодувати для передачі.

Кодер складається із двох частин, перша частина називається кодер джерела, точна назва залежить від типу джерела. Джерелам різних типів даних відповідають різні типи кодерів.

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

Відповідно до моделі, малюнку 10.1 канал передачі даних піддається впливу «додаткового випадкового шуму». Весь шум у системі об'єднаний у цій точці. Передбачається, що кодер приймає всі символи без спотворень, а декодер виконує свою функцію без помилок. Це деяка ідеалізація, але для багатьох практичних цілей вона близька до реальності.

Фаза декодування також складається з двох етапів: канал - стандарт, стандарт-приймач даних. Наприкінці передачі передаються споживачеві. І знову ми не розглядаємо питання, як споживач трактує ці дані.

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

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

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

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

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

Розглянемо алфавіт з небагатьох символів, зазвичай алфавіти набагато більше. Алфавіти мов починається від 16 до 36 символів, включаючи символи у верхньому та нижньому регістрі, числа знаки, пунктуації. Наприклад, у таблиці ASCII 128 = 2^7 символів.
Розглянемо спеціальний код, що складається із 4 символів s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Як приймач повинен трактувати такий отриманий вираз

Як s1s1s4або як s2s4?

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

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Декодує повідомлення унікальним способом. Візьмемо довільний рядок і розглянемо, як його декодуватиме приймач. Вам необхідно побудувати дерево декодування. Відповідно до форми на малюнку 10.II. Рядок

1101000010011011100010100110 …

Може бути розбита на блоки символів

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Відповідно до такого правила побудови дерева декодування:

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

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

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

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

Малюнок 10.II

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

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Припустимо, ми отримали послідовність 011111...111 . Єдиний спосіб, яким можна декодувати текст повідомлення: групувати біти з кінця по 3 групи і виділяти групи з провідним нулем перед одиничками, після цього можна декодувати. Такий код декодується єдиним способом, але не миттєвим! Для декодування потрібно дочекатися закінчення передачі! У практиці такий підхід нівелює швидкість декодування (теорема Макміллана), отже необхідно пошукати способи миттєвого декодування.

Розглянемо два способи кодування того самого символу, Si:

s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,

Дерево декодування цього способу представлене малюнку 10.III.

Малюнок 10.III

Другий спосіб

s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111,

Дерево декодування цього догляду представлено малюнку 10.IV.

Найбільш очевидним способом вимірювання якість коду – це середня довжина для деякого набору повідомлень. Для цього необхідно обчислити довжину коду кожного символу, помножену на ймовірність появи pi. Таким чином, вийде довжина всього коду. Формула середньої довжини коду L для алфавіту з q символів виглядає наступним чином

Де pi – ймовірність появи символу si, li – відповідна довжина закодованого символу. Для ефективного коду значення L має бути якнайменше. Якщо P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 та p5 = 1/16, тоді для коду #1 отримуємо значення довжини коду

А для коду #2

Отримані значення свідчать про перевагу першого коду.
Якщо у всіх слів в алфавіті буде однакова ймовірність виникнення, тоді кращим буде другий код. Наприклад, за pi = 1/5 довжина коду #1

А довжина коду #2

Цей результат показує перевагу 2 коди. Отже, під час створення «хорошого» коду необхідно враховувати можливість виникнення символів.

Малюнок 10.IV

Малюнок 10.V

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

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

Для доказу нерівності Крафта для будь-якого швидкого унікального коду, що декодується, побудуємо дерево декодування і застосуємо метод математичної індукції. Якщо дерево має один або два листи, як показано на малюнку 10.V, тоді без сумніву нерівність вірна. Далі, якщо дерево має більш ніж два листи, то розбиваємо дерево довгий m на два піддерева. Відповідно до принципу індукції припускаємо, що нерівність правильна кожної гілки висотою m -1 чи менше. Відповідно до принципу індукції, застосовуючи нерівність до кожної гілки. Позначимо довжини кодів гілок K" і K"". При об'єднанні двох гілок дерева довжина кожного зростає на 1, отже, довжина коду складається з сум K'/2 і K'/2,

Теорему доведено.

Розглянемо підтвердження теорема Макміллана. Застосуємо нерівність Крафта до неточно декодуємо коди. Доказ побудовано тому факті, що з будь-якого числа K > 1 n-ая ступінь числа свідомо більше лінійної функції від n, де n - досить велике число. Зведемо нерівність Крафта в n-ий ступінь і подаємо вираз у вигляді суми

Де Nk число символів довжини k, підсумовування починаємо з мінімальної довжини n-го уявлення символу і закінчуємо максимальну довжину nl, де l - максимальна довжина закодованого символу. З вимоги унікального декодування випливає, що. Сума подається у вигляді

Якщо K > 1, тоді необхідно встановити досить великим для того, щоб нерівність стала хибною. Отже, k<= 1; теорема Макмиллана доказана.

Розглянемо кілька прикладів застосування нерівності Крафта. Чи може існувати унікальний код, що декодується, з довжинами 1, 3, 3, 3? Так, оскільки

А що щодо довжин 1, 2, 2, 3? Розрахуємо згідно з формулою

Нерівність порушена! У цьому коді дуже багато коротких символів.

Точкові коди (comma codes) - це коди, які складаються із символів 1, що закінчуються символом 0, за винятком останнього символу, що складається з усіх одиниць. Одним із окремих випадків служить код

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5 = 11111.

Для цього коду отримуємо вираз для нерівності Крафта

І тут досягаємо рівність. Легко бачити, що для точкових кодів нерівність Крафта вироджується на рівність.

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

Необхідно відзначити, що нерівність Крафта говорить не про те, що цей код унікально декодується, а про те, що існує код із символами такої довжини, які унікально декодується. Для побудови унікального коду, що декодується, можна привласнити двійковим числом відповідну довжину в бітах li. Наприклад, для довжин 2, 2, 3, 3, 4, 4, 4, 4 отримуємо нерівність Крафта

Отже, може існувати такий унікальний декодований потоковий код.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

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

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

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

Далі буде...

Хто хоче допомогти з перекладом, версткою та виданням книги – пишіть у личку чи на пошту [email protected]

До речі, ми ще запустили переклад ще однієї крутої книги.

Кодування. Основні поняття.

Різні методи кодування широко використовуються в практичній діяльності людини з незапам'ятних часів. Наприклад, десяткова позиційна система числення – це спосіб кодування натуральних чисел. Інший спосіб кодування натуральних чисел - римські цифри, причому цей метод більш наочний і природний, дійсно, палець - I, п'ятірня - V, дві п'ятірні - X. Однак при цьому способі кодування важче виконувати арифметичні операції над великими числами, тому він був витіснений способом кодування заснованому на позиційній десятковій системі числення. З цього прикладу можна зробити висновок, що різні способи кодування мають властиві тільки їм специфічні особливості, які в залежності від цілей кодування можуть бути як гідністю конкретного способу кодування, так і його недоліком.

Широко відомі способи числового кодування геометричних об'єктів та їх положення у просторі: декартові координати та полярні координати. І ці способи кодування відрізняються притаманними їм специфічними особливостями.

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

- Подання даних довільної природи (чисел, тексту, графіки) в пам'яті комп'ютера;

- Оптимальна передача даних по каналах зв'язку;

– захист інформації (повідомлень) від несанкціонованого доступу;

- Забезпечення перешкодостійкості при передачі даних по каналах зв'язку;

- Стиснення інформації.

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

Кодування може бути числовим (цифровим) і нечисловим, залежно від виду, в якому представлені кодові символи: числа в системі обчислення або інші якісь об'єкти або знаки відповідно.

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

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

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

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

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

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

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

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

M = a · n. (2.1)

Найбільша кількість різних чисел, яка може бути записана в цьому пристрої N:

N = a n.

Прологарифмувавши цей вираз і висловивши з нього nотримаємо:

n= ln N/ln a.

Перетворивши вираз (2.1) на вигляд

M= a ∙ ln N/ln a(2.2)

можна визначити, за якої підстави логарифмів aкількість елементів Mбуде мінімальним при заданому N. Продиференціювавши по aфункцію M = f(a)і прирівнявши її похідну до нуля, отримаємо:

Очевидно, що для будь-якого кінцевого a

ln N/ ln 2 a ≠ 0

і, отже,

ln a - 1 = 0,

звідки a = e ≈ 2,7.

Так як основа системи числення може бути цілим числом, то авибирають рівним 2 або 3. Для прикладу поставимо максимальну ємність пристрою зберігання N=10 6 чисел. Тоді за різних підстав систем обчислення ( а)кількість елементів ( M)в такому пристрої зберігання буде, відповідно до виразу (2.2), наступні (Таблиця 2.1):

Таблиця 2.1.

а
М	39,2	38,2	39,2	42,9		91,2

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

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

Об'єктом кодування служить як дискретна, і безперервна інформація, яка надходить до споживача через джерело інформації. Поняття кодування означає перетворення інформації у форму, зручну передачі по певному каналу зв'язку.

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

Теоретично кодування існує низка напрямів:

• статичне чи ефективне кодування;
• завадостійке кодування;
• коригувальні коди;
• циклічні коди;
• арифметичні коди.

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

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

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

Якщо всі кодові слова мають однакову довжину, код називається рівномірним, або блоковим.

Під абстрактним алфавітом розумітимемо впорядковану дискретну безліч символів.

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

Де алфавіту А, безлічі слів, складених у алфавіті У. Безліч кодів букв називається безліччю елементарних кодів. Алфавітне кодування можна використовувати для будь-якої кількості повідомлень.

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

Кодування тексту

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

Проте, обмежений набір із 256 кодів символів сьогодні вже не задовольняє збільшені потреби міжнародного спілкування. Все більшого поширення набуває універсальна система 16-розрядного кодування символів UNICODE.

Потужність алфавіту в системі кодування UNICODE становить 216 = 65536 різних кодів, з яких 63484 коду відповідають символам більшості алфавітів, а 2048 кодів, що залишилися, розділені навпіл і утворюють таблицю розміром 1024 стовпців х 102 рядків. У цій таблиці більше мільйона осередків, у яких можна розмістити ще понад мільйон різних символів. Це символи «мертвих» мов, і навіть символи, які мають лексичного змісту, покажчики, знаки тощо. Для запису цих додаткових символів потрібна пара 16-розрядних слів (16 розрядів для номера рядка та 16 розрядів для номера стовпця).

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

Кодування зображень

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

Чорно-білі зображення прийнято представляти у градаціях сірого кольору, для цього використовується модель GreyScale. Якщо яскравість точки кодується одним байтом, можна використовувати 256 різних сірих тонів. Така точність узгоджується із сприйнятливістю людського ока та можливостями поліграфічної техніки.

При кодуванні кольорових зображень застосовують принцип декомпозиції кольору на складові для цього використовують модель RGB . Кольорове зображення на екрані утворюється шляхом змішування трьох базових кольорів: червоного (Red, R), синього (Blue, B) та зеленого (Green, G).

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

Кольорові дисплеї, що використовують такий принцип, називаються RGB-моніторами.

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

схема кольороутворення

Якщо всі три складові мають однакову інтенсивність (яскравість), то з їх поєднань можна отримати 8 різних кольорів (23):

			Коричневий

Формування кольорів при глибині кольору 24 біти:

Чим більша глибина кольору, тим ширше діапазон доступних кольорів і тим точніше їхнє подання в оцифрованому зображенні. Піксель з бітовою глибиною, що дорівнює одиниці, має лише 2 (у першому ступені) можливі стани — два кольори: чорний або білий. Піксель з бітовою глибиною 8 одиниць має 28 або 256 можливих колірних значень. Піксель з бітовою глибиною в 24 одиниці має 224 ступеня) або 16,7 мільйонів можливих значень. Вважається, що 24-бітові зображення, що містять 16,7 мільйонів кольорів, досить точно передають фарби навколишнього світу. Як правило, роздільна здатність задається в діапазоні від 1 до 48 біт/піксель.

При друку на папері використовується дещо інша колірна модель: якщо монітор випромінював світло, відтінок виходив у результаті складання кольорів, то фарби - поглинають світло, кольори віднімаються. Тому в якості основних використовують блакитну (Cyan, C), пурпурову (Magenta, M) та жовту (Yellow, Y) фарби. Крім того, через не ідеальність барвників, до них зазвичай додають четверту - чорну (black, K). Для зберігання інформації про кожну фарбу і в цьому випадку найчастіше використовують 1 байт. Така система кодування зветься CMYK.

Більш грубе уявлення кольору використовує менше розрядів. Наприклад, кодування кольорової графіки 16-розрядними числами зветься High Color . І тут кожному кольору відводять п'ять розрядів.

Кодування звуку та відео

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

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

Метод кодування на основі табличного синтезу застосовується тільки до музичних творів. У заздалегідь підготовлених таблицях зберігаються зразки (семпли) звуків різних музичних інструментів. Числові коди визначають інструмент, ноту та тривалість звучання.

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

04.04.2006 Леонід Черняк Рубрика:Технології

«Відкриті системи» Створення комп'ютерів було б неможливо, якщо одночасно з появою не була б створена теорія кодування сигналів Теорія кодування - одна з тих областей математики, які помітно вплинули на розвиток комп'ютера.

«Відкриті системи»

Створення комп'ютерів було б неможливим, якщо одночасно з їх появою не була б створена теорія кодування сигналів

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

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

Першим теоретичне вирішення проблеми передачі даних по зашумленим каналам запропонував Клод Шеннон, основоположник статистичної теорії інформації. Шеннон був зіркою свого часу, він входив до академічної еліти США. Будучи аспірантом Ванневара Буша, в 1940 році він отримав премію імені Нобеля (не плутати з Нобелівською премією!), що присуджується вченим, який не досяг 30 років. Працюючи в Bell Labs, Шеннон написав роботу «Математична теорія передачі повідомлень» (1948), де показав, що й пропускна спроможність каналу вище ентропії джерела повідомлень, повідомлення можна закодувати отже воно буде передано без зайвих затримок. Цей висновок міститься в одній із доведених Шенноном теорем, її сенс зводиться до того, що за наявності каналу з достатньою пропускною здатністю повідомлення може бути передано з деякими тимчасовими затримками. Крім того, він показав теоретичну можливість достовірної передачі за наявності шуму каналу. Формулу C = W log ((P+N)/N), висічену на скромному пам'ятнику Шеннону, встановленому в його рідному місті в штаті Мічиган, порівнюють за значенням формулою Альберта Ейнштейна E = mc 2 .

Праці Шеннона дали їжу для багатьох подальших досліджень у галузі теорії інформації, але практичного інженерного застосування вони не мали. Перехід від теорії до практики став можливим завдяки зусиллям Річарда Хеммінга, колеги Шеннона з Bell Labs, який отримав популярність за відкриття класу кодів, які так і стали називати «кодами Хеммінга». Існує легенда, що до винаходу своїх кодів Хеммінга підштовхнуло незручність у роботі з перфокартами на релейній лічильній машині Bell Model V у середині 40-х років. Йому давали час для роботи на машині у вихідні дні, коли не було операторів, і йому самому доводилося вовтузитися з введенням. Тим не менш, але Хеммінг запропонував коди, здатні коригувати помилки в каналах зв'язку, в тому числі і в магістралях передачі даних в комп'ютерах, насамперед між процесором і пам'яттю. Коди Хеммінга стали свідченням того, як можна практично реалізувати можливості, на які вказують теореми Шеннона.

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

Достовірно лише те, що саме Хеммінг першим запропонував коди з виправленням помилок (Error-Correcting Code, ECC). Сучасні модифікації цих кодів використовуються у всіх системах зберігання даних та для обміну між процесором та оперативною пам'яттю. Один з їх варіантів, коди Ріда-Соломона застосовуються в компакт-дисках, дозволяючи відтворювати записи без скрипів та шумів, які могли б викликати подряпини та порошинки. Існує безліч версій кодів, побудованих «за мотивами» Хеммінга, вони різняться алгоритмами кодування та кількістю перевірочних бітів. Особливого значення подібні коди набули у зв'язку з розвитком далекого космічного зв'язку з міжпланетними станціями, наприклад, існують коди Ріда-Мюллера, де на сім інформаційних бітів припадає 32 контрольні, або на шість - 26.

Серед нових кодів ECC слід назвати коди LDPC (Low-Density Parity-check Code). Взагалі вони відомі років тридцять, але особливий інтерес до них виявився саме в останні роки, коли стало розвиватися телебачення високої чіткості. Коди LDPC не мають 100-відсоткової достовірності, але ймовірність помилки може бути доведена до бажаної, і при цьому з максимальною повнотою використовується пропускна здатність каналу. До них близькі турбокоди (Turbo Code), вони ефективні при роботі з об'єктами, що знаходяться в умовах далекого космосу і обмеженої пропускної спроможності каналу.

В історію теорії кодування міцно вписано ім'я Володимира Олександровича Котельникова. У 1933 році в «Матеріалах з радіозв'язку до I Всесоюзного з'їзду з питань технічної реконструкції зв'язку» він опублікував роботу «Про пропускну спроможність?ефіру? і?дроту?». Ім'я Котельникова на правах рівного входить у назву однієї з найважливіших теорем теорії кодування. Цією теоремою визначаються умови, за яких переданий сигнал може бути відновлено без втрати інформації.

Цю теорему називають по-різному, у тому числі теорему WKS (абревіатура WKS взята від Whittaker, Kotelnikov, Shannon). У деяких джерелах використовують і Nyquist-Shannon sampling theorem, і Whittaker-Shannon sampling theorem, а у вітчизняних підручниках вузів найчастіше зустрічається просто «теорема Котельникова». Насправді теорема має довшу історію. Її першу частину 1897 року довів французький математик Еміль Борель. Свій внесок у 1915 році зробив Едмунд Уіттекер. У 1920 році японець Кінносукі Огура опублікував поправки до досліджень Уіттекера, а в 1928 році американець Гаррі Найквіст уточнив принципи оцифрування та відновлення аналогового сигналу.

Клод Шеннон(1916 - 2001) зі шкільних років проявляв рівний інтерес до математики та електротехніки. У 1932 році він вступив до Університету штату Мічиган, у 1936-му - до Массачусетського технологічного інституту, який закінчив у 1940 році, отримавши два ступені - магістра з електротехніки та доктора в галузі математики. У 1941 році Шеннон вступив на роботу в Bell Laboratories. Тут він почав розвивати ідеї, які згодом вилилися у теорію інформації. 1948-го Шеннон опублікував статтю «Математична теорія зв'язку», де було сформульовано базові ідеї вченого, зокрема, визначення кількості інформації через ентропію, а також запропонував одиницю інформації, що визначає вибір із двох рівноймовірних варіантів, тобто те, що згодом назвали бітом . У 1957-1961 роках Шеннон опублікував роботи, де доводилася теорема про пропускну спроможність зашумлених каналів зв'язку, яка тепер має його ім'я. 1957 року Шеннон став професором Массачусетського технологічного інституту, звідки пішов на пенсію через 21 рік. На «заслуженому відпочинку» Шеннон повністю віддався своєму давньому захопленню жонглюванням. Він побудував кілька жонглюючих машин і навіть створив загальну теорію жонглювання.

Річард Хемінг(1915 - 1998) почав свою освіту в університеті Чикаго, де в 1937 році отримав ступінь бакалавра. У 1939 році він отримав ступінь магістра в Університеті Небраски, а ступінь доктора математики - в Університеті Іллінойсу. В 1945 Хеммінг почав працювати в рамках Манхеттенського проекту - масштабної державної науково-дослідної роботи зі створення атомної бомби. У 1946 році Хеммінг вступив на роботу в Bell Telephone Laboratories, де працював у тому числі з Клодом Шенноном. 1976 року Хеммінг отримав кафедру у військово-морській аспірантурі в Монтерей у Каліфорнії.

Працю, яка зробила його знаменитим, фундаментальне дослідження кодів виявлення та виправлення помилок, Хеммінг опублікував у 1950 році. У 1956 році він брав участь у роботі над одним із ранніх мейнфреймів IBM 650. Його роботи заклали основу мови програмування, яку пізніше еволюціонував у мови програмування високого рівня. На знак визнання заслуг Хеммінга в галузі інформатики інститут IEEE заснував медаль за визначні заслуги у розвитку інформатики та теорії систем, яку назвав його ім'ям.

Володимир Котельников(1908 - 2005) в 1926 вступив на Електротехнічний факультет Московського вищого технічного училища імені М. Е. Баумана (МВТУ), але став випускником Московського енергетичного інституту (МЕІ), який виділився з МВТУ як самостійний інститут. Під час навчання в аспірантурі (1931-1933) Котельников математично точно сформулював та довів «теорему відліків», яка згодом була названа його ім'ям. Після закінчення аспірантури в 1933 Котельников, залишаючись викладати в МЕІ, вступив на роботу в Центральний науково-дослідний інститут зв'язку (ЦНДІС). У 1941 році В. А. Котельников сформулював чітке положення про те, яким вимогам повинна задовольняти математично недешифрована система та дано доказ неможливості її дешифрування. 1944 року Котельников обійняв посаду професора, декана радіотехнічного факультету МЕІ, де працював до 1980 року. У 1953 році у віці 45 років Котельников був обраний одразу дійсним членом Академії наук СРСР. З 1968 по 1990 В. А. Котельников був також професором, завідувачем кафедри Московського фізико-технічного інституту.

Народження теорії кодування

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

Тема 5.2. Алфавітне кодування У випадку завдання кодування можна наступним чином. Нехай задані два алфавіти А та В, що складаються з кінцевого числа символів: і. Елементи алфавіту називаються літерами. Впорядкований набір в алфавіті А назвемо словом, де позначається п =l()=| |. , число п показує кількість букв у слові і називається довжиною слова, Порожнє слово позначається: Для слова буква a1, називається початком, або префіксом, слова буква an – закінченням, або постфіксом, слова. , а Слова можна поєднувати. Для цього префікс другого слова повинен слідувати одразу за постфіксом першого, при цьому в новому слові вони, природно, втрачають свій статус, якщо одне зі слів не було порожнім. З'єднання слів позначається, з'єднання п однакових слів позначається, причому. Безліч всіх непустих слів алфавіту А позначимо А*: Безліч А називають алфавітом повідомлень, а безліч - кодуючим алфавітом. Безліч слів, складених в алфавіті, позначимо *.

Позначимо через F відображення слів алфавіту А до алфавіту В. Тоді слово назвемо кодом слова. Кодуванням називають універсальний спосіб відображення інформації при її зберіганні, передачі та обробці у вигляді системи відповідності між елементами повідомлень та сигналами, за допомогою яких ці елементи можна зафіксувати. Таким чином, код - правило однозначного перетворення (тобто функція) повідомлення з однієї символічної форми подання (вихідного алфавіту А) на іншу (об'єктний алфавіт В), зазвичай без будь-яких втрат інформації. Процес перетворення F: А* В*→ слів вихідного алфавіту А в алфавіт називається кодуванням інформації. Процес зворотного перетворення слова називається декодуванням. Отже, декодування - функція, зворотна F, тобто. F1. у слово Оскільки для будь-якого кодування має виконуватися операція декодування, то відображення має бути оборотним (бієкція). Якщо |B|= m, то F називається мічним кодуванням, найбільш поширений випадок = (0, 1) двійкове кодування. Саме цей випадок і розглядається надалі. Якщо всі кодові слова мають однакову довжину, то код називається рівномірним, або блоковим. Алфавітне (або буквене) кодування можна задати таблицею кодів. Кодом або функцією, що кодує, буде служити деяка підстановка. Тоді, де, . Таке буквене кодування позначається називається безліччю елементарних кодів. Алфавітне кодування можна використовувати для будь-якої кількості повідомлень. Таким чином, алфавітне кодування є найпростішим і його завжди можна ввести на непустих алфавітах. . Безліч кодів букв

ПРИКЛАД Нехай задані алфавіти А = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) В = (0, 1). Тоді таблиця кодування то, можливо подстановкой: . Це двойнодесяткове кодування, воно є взаємнооднозначним і тому допускає декодування. Однак схема не є однозначною. Наприклад, набір із шести одиниць 111111 може відповідати як слову 333, так і 77, а також 111111, 137, 3311 або 7111 плюс будь-яка перестановка. Схема алфавітного кодування називається префіксною, якщо елементарний код однієї літери не є префіксом елементарного коду іншої літери. Схема алфавітного кодування називається роздільною, якщо будь-яке слово, складене з елементарних кодів, розкладається на елементарні коди єдиним чином. Алфавітне кодування з схемою, що розділиться, допускає декодування. Можна довести, що префіксна схема є роздільною. Щоб схема алфавітного кодування була роздільною, необхідно, щоб довжини елементарних кодів задовольняли співвідношенню, відомому як нерівність Макміллана. Нерівність Макміллана Якщо схема алфавітного кодування

роздільна, то справедлива нерівність ПРИКЛАД Схема алфавітного кодування А = (а, b) і В = (0, 1), є роздільною, тому що, і, отже, виконується нерівність Макміллана Дана схема префіксної не є, т.к. елементарний код літери є префіксом елементарного коду літери b. Тема 5.3. Кодування з мінімальною надмірністю На практиці важливо, щоб коди повідомлень мали якомога меншу довжину. Алфавітне кодування придатне для будь-яких повідомлень, якщо про безліч усіх слів алфавіту А нічого не відомо, то точно сформулювати завдання оптимізації важко. Однак на практиці часто є додаткова інформація. Наприклад, для повідомлень, представлених природною мовою, такою додатковою інформацією може бути розподіл ймовірності появи букв у повідомленні. Тоді завдання побудови оптимального коду набуває точного математичного формулювання та суворого рішення.

Нехай задана деяка схема алфавітного кодування, що розділиться. Тоді будь-яка схема, де впорядкований набір є перестановка впорядкованого, також буде розділюваною. У разі, якщо довжини елементарних набору кодів рівні, їх перестановка у схемі впливає довжину закодованого повідомлення. У тому випадку, якщо довжини елементарних кодів різні, то довжина коду повідомлення безпосередньо залежить від того, які елементарні коди яким літерам поставлені у відповідність, і від того, який склад літер у повідомленні. Якщо задані конкретне повідомлення та конкретна схема кодування, можна підібрати таку перестановку кодів, коли він довжина коду повідомлення буде мінімальною. Алгоритм призначення елементарних кодів, при якому довжина коду фіксованого повідомлення S буде мінімальною за фіксованою схемою: відсортувати літери в порядку зменшення кількості входжень; Сортувати елементарні коди в порядку зростання довжини; ۞ поставити коди у відповідність до літер в установленому порядку. Нехай заданий алфавіт та ймовірність появи букв у повідомленні:

Де рi - ймовірність появи літери ai, причому літери з нульовою ймовірністю появи в повідомленні виключені і літери впорядковані за зменшенням ймовірності їх появи Для роздільної схеми алфавітного кодування при розподілі ймовірностей Р існує так звана середня ціна, або довжина кодування повідомлення, що позначається та визначається як ПРИКЛАД. Для схеми алфавітного кодування, що розділяється А=(а,b), В=(0,1), при розподілі ймовірностей ціна кодування становить а при розподілі ймовірностей ціна кодування становить

Тема 5.4. Кодування методом Хаффмана Цей алгоритм було винайдено 1952 року Девідом Хаффманом. Тема 5.5. Арифметичне кодування Як і в алгоритмі Хаффмана, все починається з таблиці елементів та відповідних ймовірностей. Допустимо, вхідний алфавіт складається всього з трьох елементів: a1, a2 і a3, і при цьому P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Припустимо також, що нам треба закодувати послідовність a1, a1, a2, a3. Розіб'ємо напівінтервал , де р деяке фіксоване число, 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

розсуву та одного мажоритарного елемента і виправляє одну помилку, має порядок (пор. з (2)). Як математич. моделі кодера і декодера зазвичай розглядають з хеми з функціональних елементів і під складністю розуміють число елементів у схемі. Для відомих класівкодів з виправленням помилок проведено дослідження можливих алгоритмів К. і д. і отримані верхні кордони складності кодера і декодера. Знайдені також крихі співвідношення між швидкістю передачі кодування, завадостійкістю кодування і складністю декодера (див.). Ще один напрямок досліджень у теорії кодування пов'язаний з тим, що багато результатів (напр., теорема Шеннона і кордон (3)) не є "конструктивними", а являють собою теореми існування нескінченних послідовностей (К п) кодів У зв'язку з цим робляться зусилля , щоб довести ці результати в класі таких послідовностей (К п) кодів, для крих існує машина Тьюринга, що розпізнає належність довільного слова довжини l безлічі завчасно, що має повільний порядок зростання щодо l (напр., llog l). Некри нові конструкції і методи отримання кордонів, розроблені в теорії кодування, привели до істотного просування в питаннях, на перший погляд досить далеких від традиційних завдань теорії кодування. Тут слід зазначити використання максимального коду з виправленням однієї помилки васимптотически оптимальному методі реалізації функцій алгебри логіки контактними схемами; використання нерівності (1) в оцінці складності реалізації формулами одногокласу функцій алгебри логики. Ідеї ​​та результати теорії кодування знаходять свій подальший розвиток взавданнях синтезу самокоректуючих схем і надійних схем з ненадійних елементів. Шеннон К., Роботи з теорії інформації та кібернетиці, пров. з англ., М., 1963; Берлекемп Е., Алгебраїчна теорія кодування, пров. з англ., М., 1971; Пітерсон У., Велдон Е., Коди, що виправляють помилки, пров. з англ., 2 видавництва, М., 1976; Дискретна математика та математичні питання кібернетики, т.1, М., 1974, розділ 5; Бассалиго Л. А., Зяблов Ст Ст, Пінскер М. С, "Пробл. передачі інформації", 1977, т.13, № 3, с. 517; [В] Сідельников Ст М., "Матем. Зб.", 1974, т. 95, ст. 1, с. 148 58. Ст І. Левенштейн.

Математична енциклопедія. - М: Радянська енциклопедія. І. М. Виноградов. 1977-1985.  КОДИРУВАННЯ АЛФАВІТНЕ  КОЄВКЛІДОВИЙ ПРОСТІР Див. також в інших словниках:  ДЕКОДУВАННЯ - див. Кодування та декодування … Математична енциклопедія  Кодування звукової інформації - Цю статтю слід вікіфікувати. Будь ласка, оформіть її згідно з правилами оформлення статей. В основі кодування звуку з використанням ПК лежить процес перетворення коливань повітря на коливання електричного … Вікіпедія  КОДИРУВАННЯ - (від франц. code - зведення законів, правил) - відображення (перетворення) деяких об'єктів (подій, станів) в систему конструктивних об'єктів (називаються) кодовими образами), що здійснюється за визнач. правилам, сукупність до рих зв. шифром К., … … Філософська енциклопедія  КОДИРУВАННЯ ІНФОРМАЦІЇ - встановлення відповідності між елементами повідомлення і сигналами, за допомогою яких ці елементи можуть бути зафіксовані. Нехай, безліч елементів повідомлення, А алфавіт з символами, Нехай кінцева послідовність символів зв. словом в… … Фізична енциклопедія  КОДИРУВАННЯ ОПТИМАЛЬНЕ - (в інженерній психології) (англ. optimal coding) створення кодів, що забезпечують максимальну швидкість та надійність прийому та переробки інформації про об'єкт управління людиною оператором (див. Прийом інформації, Декодування). Проблема К. о.… … Велика психологічна енциклопедія  ДЕКОДУВАННЯ (в інженерній психології) - (англ. decoding) заключна операція процесу прийому інформації людиною оператором, яка полягає у перешифруванні параметрів, що характеризують стан об'єкта управління, та у переведенні їх у образ керованого об'єкта ( див. Кодування… … Велика психологічна енциклопедія

 Декодування – відновлення повідомлення, закодованого переданими та прийнятими сигналами (див. Кодування) … Економіко математичний словник  КОДИРУВАННЯ – КОДИРУВАННЯ. Один із етапів породження мови, тоді як «декодування» – прийом та інтерпретація, процес розуміння мовного повідомлення. Див. психолінгвістика … Новий словник методичних термінів та понять (теорія та практика навчання мовам)  КОДИРУВАННЯ - (англ. coding). 1. Перетворення сигналу з однієї енергетичної форми в ін. 2. Перетворення однієї системи сигналів або знаків в ін. 3. К. (мнемічне)… … Велика психологічна енциклопедія  Декодування - Ця стаття про код у теорії інформації, інші значення цього слова див. у код (значення). Код правило (алгоритм) зіставлення кожному конкретному повідомленню строго певної комбінації символів (знаків) (або сигналів). Кодом також називається… … Оптимальне кодування Одне й те повідомлення можна закодувати різними способами. Оптимально закодованим вважатимемо такий код, при якому на передачу повідомлень витрачається мінімальний час. Якщо на передачу кожного елементарного символу (0 або 1) витрачається той самий час, то оптимальним буде такий код, який матиме мінімально можливу довжину. Приклад 1. Нехай є випадкова величина X(x1,x2,x3,x4,x5,x6,x7,x8), що має вісім станів з розподілом ймовірностей Для кодування алфавіту з восьми букв без урахування ймовірностей рівномірним двійковим кодом нам знадобляться три символи: Це 000, 001, 010, 011, 100, 101, 110, 111 Щоб відповісти, хороший цей код чи ні, необхідно порівняти його з оптимальним значенням, тобто визначити ентропію

Визначивши надмірність L за формулою L=1H/H0=12,75/3=0,084, бачимо, що можливе скорочення довжини коду на 8,4%. Виникає питання: чи можливо скласти код, в якому на одну літеру буде, в середньому доводиться менше символів. Такі коди є. Це коди Шеннона Фано та Хаффмана. Принцип побудови оптимальних кодів: 1. Кожен елементарний символ повинен переносити максимальну кількість інформації, для цього необхідно, щоб елементарні символи (0 та 1) у закодованому тексті зустрічалися в середньому однаково часто. Ентропія у разі буде максимальної. 2. Необхідно буквам первинного алфавіту, які мають більшу ймовірність, надавати короткі кодові слова вторинного алфавіту.