Главная страница  Дискретный канал связи 

[0] [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]

ГЛАВА 13

КОДЫ И АЛГОРИТМЫ ДЛЯ ДЕКОДИРОВАНИЯ МАЖОРИТАРНЫМ МЕТОДОМ

Мажоритарное декодирование - это метод декодирования, который сравнительно прост в реализации. Если желательно иметь чрезвычайно быстрые декодеры, то нужно обратиться к мажоритарным декодерам. К сожалению, они могут декодировать чрезвычайно малый класс кодов, и эти коды, как правило, слабее других. Следовательно, для практики мажоритарное декодирование имеет второстепенное значение. Несмотря на это, некоторые практические требования могут быть удовлетворены только в его рамках. Кроме того, эти коды интересны с теоретической точки зрения и открывают новые возможности теории кодов, контролирующих ошибки.

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

13.1. ДЕКОДИРОВАНИЕ МАЖОРИТАРНЫМ МЕТОДОМ

В кодах Рида-Маллера, изучавшихся в § 3.6, декодирование каждого информационного символа производилось путем нахождения большинства голосов в множестве проверочных равенств. Существуют и другие коды, которые могут быть декодированы мажоритарно. В ретроспективе история таких кодов обычн прослеживается до кодов Рида-Маллера.

Напомним, что любой линейный {п, )-код над GF (q) имеет проверочную матрицу Н, а кодовые слова удовлетворяют равен-



ству сН = 0. Если ограничиться рассмотрением /-й строки матрицы Н, то получается проверочное равенство

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

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

Определение 13.1.1. Множество проверочных равенств называется согласующимся в к-й координате, если компонента входит в каждое проверочное равенство этого множества и каждая компонента Cj (j Ф к) входит не более чем в одно проверочное равенство этого множества.

Как будет показано в приведенной ниже теореме, мажоритарный декодер оценивает ви по большинству голосов в проверочных равенствах. Априори не известно, произошла или нет ошибка в к-м принятом бите, и равная нулю величина ошибки - это один из кандидатов при таком голосовании. Если число J проверочных равенств четно, то при одинаковом числе голосов предпочтение отдается решению об отсутствии ошибок. Если / нечетно и числоошибок меньше (/ - 1)/2, то правильное решение всегда принимается большинством голосов.

Теорема 13.1.2. Если множество J проверочных равенств согласуется в к-й координате и если в принятом слове произошло не более J/2 ошибок, то компонента си оценивается правильно.

Доказательство состоит в описании процедуры исправления. Так как компонента Ck входит в каждое проверочное равенство этой совокупности, Hfij не равно нулю. Положим

Si = т] "j: Hcpt = Hi) Hi;ei.

i=0 i=--0

Деление на Hhj гарантирует, что коэффициент при в сумме равен единице. Поскольку существует J равенств, то Sj = е по меньшей мере для половины значений /; не более J/2 других отличны от нуля, и каждое из этих et входит в множество проверочных равенств не более одного раза. Следовательно, не менее J/2

) Здесь часто используется термин ортогональный. Мы избегаем этого термина, так как он широко используется в теории векторных пространств.



всех Sj равны Ch, если равно нулю, и более J/2 всех Sj равны й, если fife отлично от нуля. Поэтому находится мажоритарным решением по Sj. □

Следствие 13.1.3. Если для каждой координаты существует J проверочных равенств, которые согласуются в этой координате, то код может исправлять \ J/2 \ оишбок.

Доказательство следует непосредственно. □

Если J четно, то J/2 является целым числом и код может исправлять J/2 ошибок. Отсюда следует, что минимальное расстояние кода не меньше / -j- 1. Прямое доказательство этого факта, вклюяая случай нечетных дается в приведенной ниже теореме. Естественно назвать J + 1 расстоянием, реализуемым при мажоритарном декодировании; оно иногда обозначается через мд. Истинное минимальное расстояние может быть больше.

Теорема 13.1.4. Если для каждой координаты линейного кода существует J проверочных равенств, которые согласуются в этой координате, то минимальное расстояние кода не меньше / + I -

Доказательство. Выберем любое ненулевое кодовое слово и любую координату k, в которой находится ненулевой символ. В координате k согласуются J проверочных равенств. Каждое из них включает ненулевую компоненту Ch и поэтому должно включать хотя бы одну другую ненулевую компоненту, поскольку в правых частях всех проверочных равенств стоят нули. Следовательно, существует не менее J других ненулевых компонент. □

Следствие 13.1.5. Если для некопорой координаты циклического кода существует J проверочных равенств, которые согласуются в этой координате, то минимальное расстояние кода не меньше J + \.

Доказательство. Каждый циклический сдвиг кодового слова в циклическом коде образует другое кодовое слово того же кода; поэтому множество J проверочных равенств для одной координаты можно использовать для того, чтобы выписать множество проверочных равенств для любой другой координаты. □

Теорема 13.1.6. Пусть й-минимальное расстояние кода, дуального коду над GF (q). Тогда мажоритарный декодер для может исправить не более (п - 1) (<J - 1)"V2 ошибок.

Доказательство. Линейные комбинации строк матрицы Н образуют кодовые слова в дуальном кодеРассмотрим множество / проверочных равенств, согласующихся в первой координате. Каждое равенство содержит не менее й - 1 ненулевых компонент среди оставшихся п - I координат и каждая из оставшихся п - 1 координат не равна нулю по крайней мере в одном из / равенств.




[0] [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]

0.0151