www.chms.ru - вывоз мусора в Балашихе 

Динамо-машины  Обратные коды 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 [ 35 ] 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

(logg 16), a избыточность кода составляет 3 двоичных разряда. Такое положение мы имели в примере, рассмотренном в 1.7.1 (см. таблицу 1-8 - код, позволяющий исправлять одиночные ошибки).

Если при передаче сообщений возможны искажения вследствие помех, то избыточность может быть использована для восстановления правильного сообщения.

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

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

Пусть принято некоторое сообщение i. Если бы помех не было, то отсюда непременно вытекало бы, что переданное сообщение тоже есть i. При наличии помех может существовать несколько различных сообщений /, передача любого из которых могла бы привести к приему сообщения i. Обозначим через рг (j) условную вероятность того, что было передано сообщение /, если известно, что принятое сообщение есть i. В соответствии со сказанным выше, неопределенность того, какое сообщение было передано, при условии, что принято сообщение i, должна измеряться суммой

- S/H/)logp,(/).

Ее среднее значение

Ну (х) = - Ер/ И) log Pi {])

(где Pi - вероятность принять сообщение i) является мерой того, какова в среднем неопределенность переданного сообщения, если известно принятоесообщение. Эту величину называют условной энтропией. (В обозначении Ну (х), как и в дальнейшем, буква х относится к передаваемым сообщениям, у - к принимаемым).

Условная энтропия переданных сообщений при известных принятых сообщениях - Ну (х) - является мерой



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

Я (л;) - Ну (X),

где Н (х) - энтропия передаваемых сообщений, т. е. количество информации, содержащейся в каждом передаваемом сообщении.

Рассмотрим следующий пример. Пусть каждое сообщение представляет собой 8-разрядное двоичное число, и пусть вероятность ошибки в каждом из разрядов р равна 1/8- Каково максимальное количество информации, которое может содержаться в каждом принятом сообщении?

Поскольку вероятность ошибки в любом из 8 разрядов сообщения равна Vs. в среднем в каждом сообщении принимается неверно 1 двоичный разряд из восьми. Но это не означает, конечно, что количество информации в каждом принятом сообщении может быть равно 7 двоичным разрядам, так как заранее не известно, какой именно из восьми двоичных разрядов принят неверно. В соответствии со сказанным выше, максимально возможное количество информации подсчитывается следующим образом.

В переданном сообщении каждый двоичный разряд может содержать максимум 1 двоичный разряд информации (если вероятности передачи О и 1 равны между собой). Тогда и вероятности приема О и 1 равны между собой (Ро = Pi = У г)- Но если принят О, то вероятность того, что был передан О, равна

Ро (0) = /8,

а вероятность того, что была передана 1, равна

Ро (1) = Vs.

Аналогичным образом

Pi (1) = Vs, Pi (0) = Ve.



Поэтому потеря информации при передаче каждого двоичного разряда (измеренная в двоичных разрядах) равна

Ну {X) = - Ро [Ро (0) Iog2 Ро (0) + ро (1) Iog2 Ро (1)] - - Pi [Pi (1) logs Pi (1) + Pi (0) logs pi (0)] =

7 7 1 1

= --g-log2-g--glog2-g-0,54 двоичного разряда.

Потеря информации во всем сообщении равна 8-0,54= =4,32 двоичного разряда, а максимальное количество информации во всем принятом сообщении составляет 8- -4,32=3,68 двоичного разряда.

Можно показать, далее, что вычисленная указанным образом потеря информации Ну (л:) равна такой величине избыточности кода, которая является необходимой и достаточной для того, чтобы вероятность правильного приема сообщения была как угодно близка к единице. Таким образом, например, передавая 3,68 двоичного разряда информации при помощи 8-разрядного двоичного кода, возможно в принципе так составить код, что все воз- м о ж н ы е ошибки будут исправлены с вероятностью как угодно близкой к единице (при условии, что при передаче одного сообщения искажается в среднем один двоичный разряд); если избыточность кода будет меньше, то при данном уровне помех это невозможно.

Более низкому уровню помех соответствует меньшая потеря информации и, следовательно, меньшая необходимая и достаточная избыточность кода. Например, если бы вероятность ошибки в каком-либо разряде равнялась Р = Vs, то потеря информации в каждом разряде была бы равна

fy{х) = - ~Iog2- 4 Iog2 Y ~ \j№OWiiiOTO разряда.

В 8-разрядном сообщении можно было бы иметь примерно 4 разряда информации (при избыточности в 4 двоичных разряда) и т. д.

Нетрудно видеть, что сформулированный здесь критерий существенно отличается от критериев, приведенных в 1.7.1 и 1.7.2.

С точки зрения критериев теории информации коды Хемминга весьма далеки от оптимальных. Из таблицы



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 [ 35 ] 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189