У. Питерсон - Коды, исправляющие ошибки (1267328), страница 33
Текст из файла (страница 33)
Тогда любому подмножеству ребер можно поставить в соответствие двоичный набор длины и, 1-я компонента которого равна 1, если 1-е ребро входит в подмножество, и равна О, если это не так. Например, совокупности из трех ребер (2, 3 и 8-го), входящих в «сечение» (см. фиг. 5.3), соответствует двоичный набор из 15 компонент (О!1 0000! 0000000). С любым линейным графом можно связять два типа кодов: 1, Циклоеой код графа — это совокупность наборов длины и, которые соответствуют циклам (замкнутым путям по графу) и объединениям непересекающихся циклов.
Эта совокупность образует аддитивпую группу по модулю 2, поскольку сумма по модулю 2 двух циклов дает либо третий цикл, либо объединение непересекающихся циклов. 2. Сечение графа — это совокупность ребер, пересекаемых линией, которая разбивает совокупность вершин графа на два стремится к нулю при г, стремящемся к бесконечности, и, следова. тельно, становится меньше, чем значение, которое гарантируется границей Варшамова — Гилберта. Кроме того, описанная система декодирования неоптимальна, так что исправляются даже не все ошибки, которые могли бы быть исправлены в соответствии с равенством (5.9).
Рассматриваемый код оказался удачным из-за того, что он исправляет подавляющее большинство наиболее вероятных комбинаций ошибок, многие из которых содержат значительно больше чем Щ2 ошибок. При определекных условиях произведения кодов эквивалентны циклическим кодам. Зги коды рассматриваются в равд. 812. Вар Фаг. 6.3. Граф Питереонге а=15, т=10. непересекающихся подмножества. Отсекаемый код зрафа состоит из совокупности наборов длины п, которые соответствуют его сечениям и объединениям непересекающихся сечений.
Эта совокупность наборов длины п также образует аддитивную группу по модулю 2, поскольку сумма по модулю 2 двух сечений приводит либо к третьему сечению, либо к объединению непересекающихся сечений. Примеры сечения и цикла показаны на фиг.
5.3. Можно доказать (например, индукцией по н), что размерность линейного подпространства циклов равна и — гл+ 1 и что размерность подпространства сечений равна т — 1. Поскольку сечение всегда пересекается с циклом в четном числе мест, то скалярное произведение набора„соответствующего циклу, и набора, соответствующего сечению, равно нулю. Таким образом, цикловой код ~рафа является нулевым пространством для отсекаемого кода, и наоборот. Минимальное расстояние для циклового (отсекаемого) кода ~Рафа в точности равно числу ребер цикла (сечения), имеющего наименьшее число ребер. В цикловом (15,6)-коде графа на фиг,5.3 '1= 5; в отсекаемом (15,9)-коде графа г( = 3. Для цикловых кодов "~ ~т, поскольку никакой цикл не может содержать ветвей льше, чем вершин. для того чтобы минимальное расстояние отсекаемого кода ь'ло равно и', каждая вершина графа должна иметь степень, не меньшую чем (, . е.
Из ее должно выходить по меньшей мере ( р~б~р Поскольку любое ребро выходит из двух вершин, то отсюда следует, что п% —. пш г Однако в этом случае А = т — 1; следовательно, 0ч. 2[ — „~ <[ — ~. (5.10) В работе Хакими и Франка (134) описан метод построения отсекаемых кодов, для которых достигается эта граница. Заметим, что для этих кодов либо 4 либо )т должны быть малы. Можно доказать, что для любого плоского графа (графа, который может быть изображен на плоскости так, чтобы его ребра при этом не пересекались) существует двойственный граф, который также является плоским.
Отсекаемый код для одного из этих графов является цикловым кодом для другого графа, и наоборот. Таким образом, неравенства (5.10) справедливы также для цикловых кодов плоских графов. Более того, если код плоского графа не содержит, повторяющихся символов, то, используя формулу Эйлера и — пч= число граней — 2, относительно просто показать, что и' ( 5. (Грань — это часть плоскости, ограниченная ветвями н не содержащая ни ветвей, ни вершин.) Таким образом, в этом случае как отсеченные, так и цикловые коды имеют плохие кодовые расстояния. Вопросами построения неплоских цикловых кодов занимались несколько исследователей„ но пока что с ограниченным успехом.
Среди наилучших известных кодов, приведенных в табл. 5.4, только относительно (9,4 и 5,3)-кодов известно, что они являются цикловыми; даже для не слишком больших значений п построение хороших кодов является трудной задачей. Это натолкнуло некоторых исследователей на поиски расширенных цикловых кодов, т. е. кодов, порожденных совокупностью линейных независимых циклов графа и некоторых других линейно независимых наборов длины и. Было предложено несколько вычислительных методов выбора этих дополнительных наборов длины и, и во многих случаях полученные коды оказались только незначительно хуже наилучших известных кодов (135), Возможно, что наиболее привлекательной стороной расширенных цикловых кодов является то, что при их декодировании можно использовать мажоритарную технику [32, 1351. (См.
гл. 1О.) Однако, как становится теперь ясно, реализация этих кодов оказывается несколько более сложной, чем реализация циклических кодов, исправляющих случайные ошибки, которые рассматри. ваются в гл. 8 — 10. б.й. Низкоплотностные коды Н соответствии с первоначальным определением Галлагера (102), двоичным низкоплотностным кодом с проверками на четность называется нулевое пространство матрицы Н размерности (ив й)к' п, в каждой строке которой содержится К единиц, а в каждом столбце — 1 единиц. Поскольку К(а — А) = Уи, то скорость передачи кода л' задается равенством Х гг = 1 — —.
К Эти коды получили название низкоплотностных, поскольку целые числа У и К обычно выбирают относительно малыми, как правило, меньше чем 0,02п. Каждый символ кодового слова в пизкоплотностном коде входит обязательно в У проверочных соотношений, определяемых строками матрицы Н. Рассмотрим ( проверочных сумм, используемых для проверки некоторого фиксированного символа. Так как плотность единиц в матрице Н довольно мала, очень немногие из остальных п — 1 символов войдут более чем в одну из этих 1 сумм (а чаще всего не войдет ни один из этих символов).
Поэтому более правдоподобно, что искаженный в результате передачи символ войдет в большее число неправильных проверочных соотношений, чем символ, переданный правильно. Отсюда вытекает, что разумной процедурой декодирования будет такая, когда принимается решение, что символ искажен, если более чем Х проверочных символов, которые от него зависят, неправильны. Параметр Х выбирается в зависимости от вероятности ошибки в канале и от кода. Несколько лучшие результаты получаются, если в качестве Х взять переменную величину (305). Тогда процедура декодирования состоит в следующем. Исследуется совокупность У проверочных сумм, связанных с первым символом полученного слова.
Если все эти суммы равны 1, то изменяется первый символ и вычисляются заново все проверочные суммы; в противном случае ничего не меняется. Последовательно исследуются полученные символы в послс проверки и-го символа возвращаются к первому символу, затем вся процедура повторяется сначала. Если в последних л испытаниях не было сделано никаких изменений.
решающее правило меняется таким образом, чтобы производить изменения, если только У вЂ” 1 или больше проверочных сумм будут равны 1. Действуя аналогично до тех пор, пока не окажется, что в последних п испытаниях не было сделано никаких изменений, затем уменьшаем порог снова на 1.
Галлагер 1102) также предложил более сложную процедуру декодирования, в которой учитываются апостериоряые вероятности на демодуляторе. Посредством рассуждений, основанных на принципе случайного выбора кода (см. гл. 4), Галлагер показал, что средняя вероятность ошибочного декодирования при использовании его алгоритма экспоненциально стремится к нулю при увеличении длины кода, хотя и не так быстро, как для соответствующего класса кодов вообще (в предпо.ложении, что рассматривается канал без памяти с двоичным входом и непрерывным выходом). Только что описанные низкоплотностные коды не получили широкого распространения на практике, как это было с некоторыми другими кодами, представленными в этой книге.
Однако алгоритмы декодирования, предложенные для этих кодов, послужили основой для многих работ по мажоритарному декодированию, которое рассматривается в гл. 10. 5.10. Каскадные коды ч ории (91] разработал метод комбинирования двух кодов для образования большего кода, который в некоторой степени напоминает умножение кодов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
