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

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

Шаг 3. Покажем, что полученное на втором шаге выражение для Ml позволяет разрешить рекуррентное соотношение, выведенное на первом шаге:

- i (Л

/=0

Mr =

= {q- 1) Д (,.)f7-<->(<7- 1)-1 =

= (<?-!)

9-(*-»(9-

*= (9-1) (l-l/-?)

9М =

= (9-1)

= (9-1) S Я"--

qi--d*+i „ 1.

Это и завершает доказательство. □

Следствие 14.1.3. Распределение весов (п, к)-кода над GF (q) с максимальным расстоянием дается соотношениями Ло = 1, Л, = О при I = 1, d* - \ и

Л=(П Т {-\)i[\]{q-*+--\)

при 1 d*.

Доказательство. Воспользуемся тождеством

(Г)+(;:;

и перепишем доказываемое равенство в виде I-,

А=(:) д(-1)(Г)+(;:;)](---)-=(:)[Т(-1)(7)(«---)-

i-d*+i -1

- Т (-1)--(; ,)(9-*+---1)

=(;)¥(-!)( 7 )(?-1)?---

Последнее равенство вытекает из теоремы 14.1.2.

l-d*



0

8,22 X 10

9,59 X Юо

2,62 X 102

4,67 X 10

7,64 X 10*

1,07 X 10«

1,30 X 10

1,34х 108

),17х10«

8,37 X 10«

4.81 X 10"

2,13 X 10

6,83 X 10

1,41 X 10

1,41 X 10"

Рис. 14.1. Распределение весов (31, 15)-кода Рида-Соломона.

Следствие 14.1.3 полезно при нахождении распределения весов кодов Рида - Соломона, например распределения весов (31, 15)-кода Рида-Соломона, приведенного на рис. 14.1. Даже для таких кодов Рида - Соломона небольшой мощности число кодовых слов веса I может быть очень большим. Вот почему, вообще говоря, практически невозможно найти распределение весов кода простым перебором кодовых слов.

В случае кодов, не являющихся кодами с максимальным расстоянием, не существует правила, аналогичного теореме 14.1.2,



При небольших п распределение весов может быть найдено поиском на ЭВМ, но с ростом п этот метод быстро становится непрактичным.

В настоящее время наиболее сильным инструментом являются выражения, устанавливающие связь между распределением весов линейного кода и распределением весов его дуального кода - так называемые тождества Мак-Вильямс. Тождества Мак-Вильямс справедливы для любого линейного кода; они вытекают из векторной структуры линейного кода и из того факта, что дуальный коду код является ортогональным дополнением Прежде чем переходить к выводу тождеств Мак-Вильямс, мы должны вернуться к изучению абстрактных конечномерных векторных пространств, начатому в § 2.6. Необходимо ввести понятия пересечения и прямой суммы двух подпространств и доказать их некоторые свойства.

Пусть и а V - подпространства пространства FK Тогда и V называется пересечениси U и V и означает множество векторов, принадлежащих и U, и V; UQ)V называется прямой суммой и и V и означает множество всех линейных комбинаций аи + bv, где и и v принадлежат соответственно U и V, а а и b - скаляры. Как U С\ V, так и U®V являются подпространствами в F".

Теорема 14.1.4.

dim [и П V] + dim [U ф V] = dim lU] -f dim [V].

Доказательство. Базис подпространства U [] V состоит из dim lU n У]"векторов. Этот базис может быть расширен до базиса и добавлением dim [U] - dim [U f] V] базисных векторов и до базиса V добавлением dim IV] - dim [U fl V] базисных векторов. Все эти базисные векторы в совокупности образуют базис подпространства U @ V. Таким образом,

dim [U @ V] = dim lU Г\ V] +

+ dim W] - dim lU П V] + dim IV] - dim lU f] V],

откуда следует теорема. □

Теорема 14.1.5.

f/J- П = (f/ ©

Доказательство. Подпространство U содержится в U @ V, и поэтому (U ф содержится в U--. Аналогично (U @ V)- содержится в V-. Следовательно, (U © V) содержится в (] [] V-.C другой стороны, запишем элемент из U @ V как аи + bv и обозначим через w любой элемент из U->- [] V. Тогда w-(ai\ + + bv) = О, и, следовательно, П содержится в ([/ ф У)-Отсюда следует, что эти два множества совпадают. □




[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.0209