On distributions of weight spectra for random linear binary codes.pdf Рассмотрим N-мерное линейное пространство BN = GF(2)N = {X = ( x i , . . . , xN) :x i , . . . ,Xn E GF(2)}. Под линейным кодом размерности k понимается k-мерное под-пространство L С BN (см. [1, 2]).Весом w(X) двоичного вектора X = (x1 , . . . , x ^ ) E Bn называется количествоненулевых координат в векторе X. Через BN и B^s будем обозначать соответственномножества векторов фиксированного веса s и веса, не превосходящего s, в Bn :B s = { X E B n : w(X) = s} , B^s = { X E B n : w(X) ^ s} ,Nтогда Bn = LI Bs.s=0Пусть vs(L) = |L П BN | и v^s(L) = |L П B^s| -количество векторов веса s и количе-ство векторов веса не больше s в линейном коде L; набор { v s ( L ) } N 0 называют весовымспектром кода L.Теорема 1. Если L - случайный k -мерный код в BN , имеющий равновероятноераспределение на множестве всех таких кодов, то при s = 1 , . . . , NE v ( L ) = C s 2k - 1 D v ( L ) = C s ^ - 1) (2 N - 2k) ЛE v s ( L ) = , D v s ( L ) = CN ( 2 N - I ) (2N - 2) I,1 - 2 N - Tи при s, t E { 1 , . . . , N } , s = t,(2k - 1)(2n - 2k)c o v ( v s ( L ) , v t ( L ) ) = - C N C w ( 2 N - 1 ) 2 ( 2 N - 2)Теорема 2. При s = 1 , . . . , N2 1 s (2fc - 1) (2N - 2k) / 1 s \ s^ < L > = 2 N - T S C N Dv< ' < L > = ^ V - 2 / i1 - 2 N -TСледствие 1. Если L С BN - случайное равновероятное k-мерное подпростран-ство и ^(L) = min{w(x) : x E L\{0}}, то2fc 1 ^ P{^(L) ^ s} ^ Ev^s(L).1 + 2 2N-T(Ev^s ( L ) ) - 1Теорема 3. Если X и Y - независимые случайные векторы из BN, причем Xимеет равномерное распределение на BN, а Y - равномерное распределение на BN, топри |s - t| ^ m ^ min{s + t, N}t + s-m t-s+m C 2 C 2P { w ( X 0 Y) = m} = p(N)(t, s, m) d=f - N-s I{m = t + s (mod 2)},CNEw(X 0 Y ) = s + t - f . Dw(X ® Y ) = 4 .Теорему 3 можно использовать для вычисления моментов суммve*(X1,...,Xn) = . /{ 4 = G{0,1,..., N}«1,...,ап=0 ^ =1где X 1 , X 2 , . . . , X n G Bn -независимые случайные векторы, распределения которыхинвариантны относительно перестановок координат.Теорема 4. Пусть X 1 , . . . , X n - независимые случайные векторы, имеющие рав-номерное распределение на BSN, тогдаNP { X 1 , . . . , Xn линейно зависимы} ^ -N. C2 t= yNt=0 C s, cN,s,t \ cN,s,t 1 + - I - n ^C: s 1 C Nг д е CN,s,t = . ( - ! ) ' " C j C N - t

Скачать электронную версию публикации