 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Элементы теории кодирования
Кодирование информации.
Примеры кодирования.
Кодирование чисел в разных системах счисления
2. Кодирование чисел в памяти компьютера - типы: byte, integer, longint, real.
Кодирования геометрических объектов формулами с помощью декартовых координат.
4. Кодирование текстовой информации:
a. Азбука Морзе.
Азбука Морзе — это схема алфавитного кодирования, где по историческим и техническим причинам 0 называется точкой и обозначается знаком «•», а 1 называется тире и обозначается знаком «-». Непосредственно проверяется, что неравенство Макмиллана(см.ниже) для азбуки Морзе не выполнено, и, следовательно, эта схема не является разделимой. На самом деле в процессе передачи информации с использованием азбуки Морзе имеются дополнительные элементы — паузы между буквами (и словами), которые позволяют декодировать сообщения. Эти дополнительные элементы определены неформально, поэтому прием и передача сообщений с помощью азбуки Морзе, особенно с высокой скоростью, является некоторым искусством, а не простой технической процедурой.
Схема кодирования Морзе:
| Символ | Код | Символ | Код | Символ | Код | Символ | Код | Символ | Код | |||||
| А | .- | Л | .-.. | Ц | -.-. | .---- | . | ...... | ||||||
| Б | -... | М | -- | Ч | ---. | ..--- | , | .-.-.- | ||||||
| В | .-- | Н | -. | Ш | ---- | ...-- | ; | -.-.-. | ||||||
| Г | --. | О | --- | Щ | --.- | ....- | : | ... | ||||||
| Д | -.. | П | .--. | Ы | -.-- | ..... | ? | ..--.. | ||||||
| Е | . | Р | .-. | Ь,Ъ | -..- | -.... | ! | --..-- | ||||||
| Ж | ...- | С | ... | Э | ..-.. | --... | () | -.--.- | ||||||
| З | --.. | Т | - | Ю | ..-- | ---.. | / | ------ | ||||||
| И | .. | У | ..- | Я | .-.- | ----. | ||||||||
| Й | .--- | Ф | ..-. | ----- | ||||||||||
| К | -.- | Х | .... |
| Вступление в pаботу (сеpия букв ЖЖ) | ...-...-...- | Знак конца (ЕЦ) | .-.-. |
| Начало пеpедачи | -.-.- | Полный конец (СК) | ...-.- |
| Знак pаздела | -...- | Номеp (pаздельно НР) | -..-. |
| Знак ошибки (сеpия pаздельных точек) | ...... | "Ждать" | .-... |
b. таблица АSCII.
A merican S tandard C ode for I nformation I nterchange
Стандартная таблица ASCII (десятичные коды символов 0 - 127)
┌────────────┬────────────┬────────┬───────┬───────┬───────┬───────┬───────┐
| 000 (nul) | 016 (dle) | 032 sp | 048 0 | 064 @ | 080 P | 096 ` | 112 p |
| 001 (soh) | 017 (dc1) | 033! | 049 1 | 065 A | 081 Q | 097 a | 113 q |
| 002 (stx) | 018 (dc2) | 034 " | 050 2 | 066 B | 082 R | 098 b | 114 r |
| 003 (etx) | 019 (dc3) | 035 # | 051 3 | 067 C | 083 S | 099 c | 115 s |
| 004 (eot) | 020 (dc4) | 036 $ | 052 4 | 068 D | 084 T | 100 d | 116 t |
| 005 (enq) | 021 (nak) | 037 % | 053 5 | 069 E | 085 U | 101 e | 117 u |
| 006 (ack) | 022 (syn) | 038 & | 054 6 | 070 F | 086 V | 102 f | 118 v |
| 007 (bel) | 023 (etb) | 039 ' | 055 7 | 071 G | 087 W | 103 g | 119 w |
| 008 (bs) | 024 (can) | 040 (| 056 8 | 072 H | 088 X | 104 h | 120 x |
| 009 (tab) | 025 (em) | 041) | 057 9 | 073 I | 089 Y | 105 i | 121 y |
| 010 (lf) | 026 (eof) | 042 * | 058: | 074 J | 090 Z | 106 j | 122 z |
| 011 (vt) | 027 (esc) | 043 + | 059; | 075 K | 091 [ | 107 k | 123 { |
| 012 (np) | 028 (fs) | 044, | 060 < | 076 L | 092 \ | 108 l | 124 | |
| 013 (cr) | 029 (gs) | 045 - | 061 = | 077 M | 093 ] | 109 m | 125 } |
| 014 (so) | 030 (rs) | 046. | 062 > | 078 N | 094 ^ | 110 n | 126 ~ |
| 015 (si) | 031 (us) | 047 / | 063? | 079 O | 095 _ | 111 o | 127 |
└────────────┴────────────┴────────┴───────┴───────┴───────┴───────┴───────┘
Расширенная таблица ASCII (десятичные коды символов 128 - 255)
┌─────────┬───────┬───────┬───────┬────---┬────---┬───────┬───────┬─────────┐
| 128 А | 143 П | 158 Ю | 172 м | 186 ║ | 200 ╚ | 214 ╓ | 228 ф | 242 Є |
| 129 Б | 144 Р | 159 Я | 173 н | 187 ╗ | 201 ╔ | 215 ╫ | 229 х | 243 є |
| 130 В | 145 С | 160 а | 174 о | 188 ╝ | 202 ╩ | 216 ╪ | 230 ц | 244 Ї |
| 131 Г | 146 Т | 161 б | 175 п | 189 ╜ | 203 ╦ | 217 ┘ | 231 ч | 245 ї |
| 132 Д | 147 У | 162 в | 176 ░ | 190 ╛ | 204 ╠ | 218 ┌ | 232 ш | 246 Ў |
| 133 Е | 148 Ф | 163 г | 177 ▒ | 191 ┐ | 205 ═ | 219 █ | 233 щ | 247 ў |
| 134 Ж | 149 Х | 164 д | 178 ▓ | 192 └ | 206 ╬ | 220 ▄ | 234 ъ | 248 ° |
| 135 З | 150 Ц | 165 е | 179 | | 193 ┴ | 207 ╧ | 221 ▌ | 235 ы | 249 ∙ |
| 136 И | 151 Ч | 166 ж | 180 ┤ | 194 ┬ | 208 ╨ | 222 ▐ | 236 ь | 250 · |
| 137 Й | 152 Ш | 167 з | 181 ╡ | 195 ├ | 209 ╤ | 223 ▀ | 237 э | 251 √ |
| 138 К | 153 Щ | 168 и | 182 ╢ | 196 ─ | 210 ╥ | 224 р | 238 ю | 252 № |
| 139 Л | 154 Ъ | 169 й | 183 ╖ | 197 ┼ | 211 ╙ | 225 с | 239 я | 253 ¤ |
| 140 М | 155 Ы | 170 к | 184 ╕ | 198 ╞ | 212 ╘ | 226 т | 240 Ё | 254 ■ |
| 141 Н | 156 Ь | 171 л | 185 ╣ | 199 ╟ | 213 ╒ | 227 у | 241 ё | 255 |
| 142 О | 157 Э | | | | | | | |
└─────────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴─────────┘
Задачи, решаемые посредством кодирования:
Представление данных(приспособление формы данных к конкретному каналу связи или какому-либо другому устройству, предназначенному для преобразования или хранения информации).
Защита информации от несанкционированного доступа.
Обеспечение помехоустойчивости при передаче данных по каналам связи.
Сжатие информации.
Трансляция и компиляция кода программ.
Элементы теории кодирования.
$1.1. Понятие кодирования.
Пусть A={ a1, a2, …, an} - конечное упорядоченное множество символов, называемое алфавитом. Под словом в алфавите A будем понимать любую конечную последовательность символов из A. Длиной слова назовем количество букв его составляющих.
Обозначим через A* - множество слов в алфавите A.
Кодом назовем любую конечную совокупность слов {x1, x2,..., xk} в некотором алфавите A.
Определение. Кодирование - операция отождествления символов или групп символов одного кода с символами или группами символов другого кода.
Пример. Арабская запись целых чисел à формат integer.
Необходимость кодирования возникает прежде всего из потребности приспособить форму сообщения к данному каналу связи или какому-либо другому устройству, предназначенному для преобразования или хранения информации. Так, с помощью телеграфных кодов сообщения, представленные в виде последовательности букв, например, русского языка, и цифр, преобразуются в определенные комбинации посылок тока.
Пусть A,B – алфавиты, S – конечная последовательность слов в алфавите А. Назовем S сообщением.
Тогда с математической точки зрения кодирование - отображение F: S->B*.
Если |B|=m, то мы имеем m-ичное кодирование. Например, B={0,1}, m=2, – имеем двоичное кодирование.
Функция F-1,если существует, называется декодированием.
Типичная задача кодирования - при данных алфавитах А и В и множестве сообщений S, найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле.
В качестве основных свойств кодирования назовем следующие:
- существование декодирования;
- помехоустойчивость или исправление ошибок: функция декодирования обладает таким свойством, что F-1(b)=F-1(b’), если b’ в определенном смысле близко к b;
- заданная сложность или простота кодирования и декодирования. Например в криптографии(шифровании) изучаются такие функции F, что F – достаточно простая функция, а F-1 требует очень сложных вычислений.
$1.2. Алфавитное кодирование
Алфавитное кодирование(АК) – кодирование, при котором код сообщения строится из кодов его элементарных частей, при этом элементарной частью сообщения является буква.
Таким образом, АК задается схемой r = {a1 => x1, a2=>x2,..., ak=>xk}, где А={a1, a2,..., ak} – алфавит, xi – элементарные коды.
Примеры.
1. A={0,1,2,...,9}, B={0,1}
r = (1=>1, 2=>10, 3=>101,..., 9=>1001) – неоднозначна: Fr(333)=Fr(77)
2. A={0,1,2,...,9}, B={0,1}
r = (1=>0001, 2=>0010, 3=>0101,..., 9=>1001) – двоично- десятичное кодирование.
Понятия: равномерное кодирование – кодирование, при котором длины элементарных кодов букв равны.
$ 1.3. Разделимые и префиксные схемы кодирования
Схема кодирования(код) называется разделимой, если любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
Схема кодирования(код) называется префиксной, если элементарный код каждой буквы не является началом(префиксом) элементарного кода другой буквы. Так, код {a,bc,cc} является префиксным, в отличие от кода {a,ab,cc}.
Если рассматривать префиксный код в двоичном алфавите, т.е. в алфавите, состоящем из двух символов, то такой код называется двоичным (или бинарным) префиксным кодом. Например, префиксный код {+,--,-+} является двоичным.
Ниже будем рассматривать только бинарные схемы кодирования. В дальнейшем слово "бинарные" может быть опущено.
Как же можно получить префиксные коды? Существует несколько методов. Мы рассмотрим метод двоичных деревьев, метод Левенштейна, кодирование Хаффмена.
Поиск по сайту: