Главная страница  История развития электросвязи 

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 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215

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

Характерной особенностью этих кодов является также и то, что информационные и проверочные элементы связаны между собой зависимостями, описываемыми линейными уравнениями. Отсюда возникает и второе название систематических кодов - линейные.

Код Хемминга. Рассмотрим в качестве примера построение систематического кода с кодовым расстоянием do = 3 (кода Хемминга). Пусть число сообщений, которое необходимо передать, равно 16. Тогда необходимое число информационных элементов к- \0g2Na = 4. Можно выписать все 16 кодовых комбинаций, включая нулевую (0000). Это один из возможных способов задания исходного (простого) кода. Другой способ заключается в выписывании только четырех кодовых комбинаций простого кода в виде матрицы, называемой единичной:

1000 0100 0010 0001

(12.1)

Суммируя по модулю два в различном сочетании кодовые комбинации, входящие в единичную матрицу, можно получить 15 кодовых комбинаций, 16-я - нулевая. Кодовые комбинации, составляющие матрицу (12.1), линейно независимы. Можно было бы составить матрицу и из других кодовых комбинаций (лишь бы они были линейно независимыми). Ненулевые комбинации Ai, А2, A3, At линейно независимые, если qHi ® Q2A2 @ ЯзАз @ ЯаАа О, где q, е {0,1} при условии, что хотя бы один из коэффициентов q, ?t 0. Дополним каждую кодовую комбинацию в (12.1) проверочными элементами так, чтобы обеспечивалось do = 3. Будем иметь в виду также тот факт, что к числу разрешенных комбинаций корректирующего кода принадлежит и комбинация 0000 ... О, называемая нулевой. Очевидно, что в числе добавляемых проверочных элементов должно быть не менее двух единиц. Тогда общее число единиц в каждой комбинации кода получим не меньше трех и комбинации, полученные нами, будут отличаться от нулевой, по крайней мере, в трех элементах. Добавим по две единицы к каждой строке матрицы (12.1):

100011 010011 001011 000111

(12.2)

Складывая строки 1 и 2 матрицы (12.2) по модулю два



1000111 0100101 0010011 0001110

(12.3)

Добавляемые проверочные элементы могут быть записаны и в другом порядке. Необходимо лишь обеспечить do = 3.

Матрицу (12.3) называют производящей, или порождающей, матрицей кода (7,4), содержащего семь элементов, из которых четыре информационных. Обычно матрицу обозначают буквой G с индексом, указывающим, к какому коду она относится (в нашем случае G(7,4)). Производящая матрица состоит из двух матриц - единичной (размерности к-к) и Cr,k), содержащей г столбцов и к строк. Суммируя в различном сочетании строки матрицы (12.3), получаем все (кроме нулевой) комбинации корректирующего кода с сзЬ = 3.

Обозначим элементы комбинации полученного семиэлементного кода ai, аг, Эз, а4, as, а, а?, из которых ai, Эг, аз, а - информационные и as, Эе, aj - проверочные. Последние могут быть получены путем суммирования по модулю два определенных информационных элементов. Разумеется, правило формирования проверочного элемента а, для любой кодовой комбинации одинаково.

Найдем правило формирования элемента as, пользуясь матрицей (12.3). Из первой строки следует, что в суммировании должен обязательно участвовать элемент ai (только в этом случае as = 1), из второй - что элемент аз в суммировании не должен участвовать, а из четвертой - что элемент а4 должен участвовать в суммировании. Итак,

а = а@а2@а. (12.4)

Уравнения для и а- по аналогии записываются в виде:

ае=а,®а@а, (12.5)

а-, = а@а2@аз. (12.6)

Алгоритм формирования проверочных элементов as, а, а? может быть задан матрицей, называемой проверочной. Эта матрица содер-

100011 010011, 110000

видим, что они отличаются только в двух элементах, т.е. заданное кодовое расстояние не обеспечивается. Дополним каждую строку проверочными элементами так, чтобы cfc = 3. Тогда матрица примет вид



(7.4)

110110011

1011010

1110001

Единицы, расположенные на местах, соответствующих информационным элементам матрицы Н(7,4), указывают на то, какие информационные элементы должны участвовать в формировании проверочного элемента. Единица на месте, соответствующем проверочному элементу, указывает, какой проверочный элемент получается при суммировании по модулю два информационных элементов. Так, из первой строки следует равенство

а, ® Эг ® а = 85.

Процедура обнаружения ошибок основана на использовании проверок (12.4)-(12.6). Очевидно, что проверочные элементы, сформированные из принятых информационных, при отсутствии ошибок должны совпадать с принятыми проверочными.

Пример 12.3. Переданная кодовая комбинация имеет вид 1000111 (первая строка матрицы (12.3)). В результате действия помех на приемном конце имеем а, аг, а, а, а, ag, а-, = 1100111. Произведем проверки (12.4)-(12.6):

а;®а2®а; =1®1©0 = 0 = а;, (12.7)

а;®а;®а; =1®0®0 = 1 = а;, (12.8)

а;©а2®а; =1©1®0 = 0 = а;. (12.9)

В то же время ag = 1, ае = 1, а = 1, т.е. а ф ag, aa-j, что говорит о наличии ошибок в принятой кодовой комбинации. При отсутствии в принятой кодовой комбинации ошибок ® aj = = О , а; ©а = = О, а; ® а = Ьз = О.

Комбинация ЬзЬгЬт называется синдромом (проверочным вектором). Равенство нулю всех элементов синдрома указывает на отсутствие ошибок или на то, что кодовая комбинация принята с ошибками, которые превратили ее в другую разрешенную. Последнее событие имеет существенно меньшую вероятность, чем первое.

Вид ненулевого синдрома определяется характером ошибок в кодовой комбинации. В нашем случае вид синдрома зависит от местоположения одиночной ошибки. В табл. 12.2 отражено соответствие между местоположением одиночной ошибки для кода, заданного матрицей (12.3), и видом синдрома.

жит Г строк И п столбцов. Применительно к сформированному нами коду (7,4) она имеет вид:



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 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215

© 2000 - 2018 ULTRASONEX-AMFODENT.RU.
Копирование материалов разрешено исключительно при условии цититирования.