Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v16(1-4)/tsymzhitov-235-272.pdf
Дата изменения: Mon Nov 26 08:15:00 2012
Дата индексирования: Thu Feb 27 22:29:05 2014
Кодировка:

ML-
. .

, , . . , , . , , 2. , ( 2 ) , ( 4 ) . : , , , , .

1.
, ML- , . , ,

236

. .

, - . , ML-. . , , , NP- [1]. , , [2]. , ML-. , , . [3]. , , . , . -, , , , 0 , , . , . -, . , . , -, , . , 0 . 3.

ML-

237

. , . [4], , . , , [5]. , , [6, 7]. [3, 4, 8, 9]. , . -, , , (. 8). , , , 0 . , , 4 5 , . . , , 2. , 0 : , 0 (. 10); , 0 (. -

238

. .

16). , ( 2 ) , ( 4 ) . , 2 , - . , , . 5 , , . (. 23), - , , , ( 3 ) . , , min-sum (sum-pro duct) , ( ) [10]. - . . ..-.. . . .

2.
. , , [11, . 1], [12, . 1] [13, . 1]. 2 . , p( ) , , 2 . , -

ML-

239

p( ), . , p( ). , p( ) = 0 2. , , r a 2 p(r a) =
=1

p(

).

p(r a) , , r , a 2 . , , , , , . , . r , c , . , , , . , , , MAP- (. maximum a posteriori decoding ). P(c r) , c , , r . MAP- r c , P(c r). , , c P(c) = -1 . , MAP- -

240

. .

ML- (. maximum likelihood decoding ), p(r c). ( ) = ln p( 0) , p( 1)

. a 2 , a = .
: =0 2

, r a p(r a) = p(r 0)
- , a

,

= ( ( 1 ), . . . , ( )).

ML- , c min, c . (1)

, , ML-, . H = ( ) в . c Hc = 0 (c) =
=1

= 0,

= 1, . . . ,

.

(1), . . (1) . = {c
2

(c) = 0 },

= 0, . . . ,

,

ML-

241

2

=

0

1

...

=.

c = arg min , c,
c

= 0, . . . ,

,

(2)

c (1), , c0 , c1 . . . , c . , c (2). , , , = 1, . . . , . , , , . . , . , , . , , , . , H , . , H, , = 1, . . . , . , H, , = 1, . . . , . , , . , = 1. . 1 [7, 4, 3]- .

242

. .
1

1 4 7 2 3 5

2

6

3

. 1. [7, 4, 3]- . , H . , . , H . , . , , / (1) . , . . 1. , , (2), ( 2 ) . 2. , 2, , (2), ( 4 ) .

3.
= { 1 } = { 1 }. a 2 su p p a = { = 1}.

ML-

243

3. a, b , a + b = , a + , b, . , b = (-1)
supp b

2

= ((-1) ).

=
supp b supp a

-
supp b supp a

=

=
supp b supp a

-
supp a

= , a + b - , a.

. , ^= 0, 1, 0, <0 ^ r
2

. , в 2 +

= . : (a, b) = .
: =

2

2 . , . , , , . , . ^ , r = (-1)^ . , (^, ) r . , 3 (^, a) = , ^ + a = r r , ^ + , a a 2 . (1) r (^, c) min, c , r

244

. .

(2) c = arg min
c

(^, c), r

= 0, . . . ,

. .

c ^ r , c0 = ^ (. 2). r

= c

c

-1 -1

c2 c1 c0 = ^ r
2

1

0

=

2

. 2. (2). min = {a
2

, a , b b

}.

, , 4. ^ min r
2

. . },

= {a
, 2

(a) = 0 (a) = 1}.

= {a

ML-

245

=

{ }.

5. c , . c + u , u , . , c + u min , u min = ((-1) ). , ,

. (c + u) = (c) + (u) = 1 + (u), (c + u) = (c) + (u) = (u) . , c+u , (u) = 1 (u) = 0 . , u , . , , = {c + u u , }. , , c + u c + u min , c+u u , . 3 , u , , u , u. , u min , . . , , . . 2 . 1. a 2 ( -), c , c = 0 supp c supp - irr a. .

, . , irr irr . 2. a, b 2 , , a b. supp(a b) = supp a supp b. 6. a 2 a = a c, a irr c . . a irr , . a / irr , c1 {0},

246

. .

a = a1 c1 a1 = 0. a1 irr , . a1 . , a = a c . . . c1 , a irr c1 . . . c . . a - a. , , , . . 7. c min = ((-1) ). , c , c 0, .

. , c = , c + c - , c 0 c . 8. c min . :

1) c , , c min / . 2) c - u , , , = ((-1) ). , c + u min . min , . , , = , = . . , u0 min , . 6 u0 - u, u0 = u c , c . , u , . c , 7 , c 0. , u0 = u c , , u0 = , u + , c , u. , u min . , , 5 c + u min . , = , irr . 8 , u min , - , , u min , . , (2):

ML-

247

min , min , , u min, u
,
0

( , c 0 c

).

(3)

, . 1 ( ). A, , 0 u = A( , , 0 ), (3). DecoderA .
: : c : c ^( ); r ; 1; , (c) = 0, u 0; ((-1) ; c c + u; { }; ; c. . .

); u A( ,

, );

+ 1;

DecoderA DecoderA ( ). 4, 8 1 9. c = DecoderA ( ), DecoderA (2), (1). , (1) (3), . ,

248

. .

. , . , 2, .

4.

, , . , 0 . , . , = 1, , , . ={ }, ={ }.

, , , , . ( )={ }, ( )={ }.

, , = { 0 }. 01 1 1 H = . . .
1

H , ( , , ).

0 . = { 1 , . . . , }, 02 . . . 0 12 . . . 1 . . , .. . . . . . 2 ...

ML-

249

H . , , , , a 2 , . , a , (
a

)=
supp a

(

a

) = su p p a.

, , (. 3). , . . , 0 , , 0 . , , 0 . , , , (3). 10. , 0 u 2 , u , 2, 0 1. . u , 0 u . , , , , 0 . . , . , ( )=
()

.

, a 2 supp a = ( ). ( ) supp a = supp u. u supp u , 0 , . 0 ( ), / ( ) . ( ) supp a

250
1

. .
1

1 4 5 4

1 5

2

3

2

2

6

3

2

6

3

1

a

1 4

2

6

3

. 3. (), = {1, 2} () a , a = (1 0 1 1 0 1) (). . , a . supp a supp u, , u irr . , u ( ). = u . ( ) supp u . supp u , , . supp u > 2, 1 , 2 supp u, 1 2

ML-

251

0 . , . 1 2 - u, supp u = 2. 0 supp u, . , , 0 supp u = 1. , u 2 . supp u = 2 ( ) 0 supp u = 1, u , 0 . c {0} supp c supp u. 0 supp u = { 0 } 1 supp c. , , 1 0 , 1 , 1 , 2 , 2 , . . . , , , 0 . , 1 , . . . , 0 . , 1 supp c 1 supp u = 2, 2 supp c. 2 , . . . , , 0 supp c. , 0 supp c = { 0 }, c . u - , , u , 0 . . , , 0 , , 0 , 0 2, 0 . , , , , 0 . , , (3). , 0 0 . , 0 . . 1) ( 2) ( )

) ( ) . ( ) .

252

. .

3) ( ) {+} ( ) {+} . 4) 5) 2. ( ) . ( )

, . , , . , . . 2. BuildTree .
: 0 : () (). : ( ) ; ( ) ; ; ( ) ; ( ) ; ; ; 0 ; , ; , ; 0; , = ( ) ; + ; ; ( ) ; - ; 0; , ( ) ; ; + 1; .

( ), + 1;

= ( ),

ML-

253

; ( ) ; ; .

BuildTree , , 0 , . , , . () () , 0 . , , , . , , 0 , , , , : , = , , = + . , : , = , > , = - . , , 0 , . , . , , () ( 0 , ( 0 ) ). . , , , = ( ). ( ) , , ,

254

. .

= + . , , , , , = ( ). ( ) , , , = . , (). 4. BuildTree
( ) ( )

( ) 0 0

(

)

(

) + +1

( ) +1 ,

. 4.

0

BuildTree.

11. BuildTree 0 : 1) ( , 0 ) , ( ) 0 , ( ) , 0 . , = ( 0 ) .

2) ( , 0 ) ( ) , 0 , ( ) . 3) () () .

ML-

255

BuildTree () () . 3. Optimize .
: . : () (). : ; ( ) +; ( ) ; ; ( ) ; ( ) = ( ) = 0, +; ; ; , ; > , - ; ( ); ( ) < ( ), ( ) ( ); ( ) ; ; ( ) ( ) - 1; ( ) = 0, ; ; ; ( ); = , ; ; ( ) ( ) + ( ); ( ) ( ) - 1; ( ) = 0, +; ;

256
; .

. .

. , () () BuildTree 0 . . , Optimize () (). ( ) +, ( ) , ( ) . , 0 . , , 0 . , 0 , ( ) , , ( ) = 0. , , , . , Optimize , BuildTree. Optimize , 0 , 0 . . , ( ) ( ), = ( ), ( ) ( ), ( ) . , ( ) . , , . , ( ) ( ), = ( ). , ( ) . , , , , . , 0 , , .

ML-

257

( , 0 ) ( , 0 ) , 0 :

={

= ( )},

={

= ( )}.

, Optimize , 0 , : ( ) ( ) , ( ) (. 5).
( ) mi n

(

) ( ) ( ) +

( ) arg min

()

(

)

(

)

. 5.

,

0

Optimize.

12. () () BuildTree 0 . Optimize : 1) ( ( ) = min ( )
,
0

) ( ) = arg min ( ).

2)

(

,

0

) +

( )=

( ).

258

. .

( , 0 ) ( , 0 ) , 0 . = {u
,
0

(

u

)},

= {u

,

0

(

u

)}.

13. () () BuildTree 0 . Optimize ( , 0 ) ( , 0 ) ( ) = min . , ( ) = min u u ( )supp u ( )supp u . ^ ( ) ^ ( ). = { }. ( ) supp u = { } ,0 u , , ^ ( ) = . . u ,0

=

+

(

)supp u

^( ) = + min
u

(

)supp u

,

u0 ,

(

)supp u0

, = min . u ( )supp u

(

)supp u

.

ML-

259

,

^( ) =

+

u . 10 supp u . supp u = { 0 }, ( ) su p p u = ( ) su p p u 0 , ,

min
u

(

= . , = + )supp u

^(

).

=

,

(

)supp u

(

0

)supp u

^ ( ) = min

, ^ ( , ( ) ^ ( ) = ( ) .

min u

= min ^ (

).

(

)supp u

) ^ ( ) ( ) 12. , ^ ( ) = ( ) ( , 0 ) ( , 0 ).

. 4. BuildSolution .
: : (). : ( ) 0; ; ; 0 ; ,
0

.

260

. .

; ( ); ( ) 1; ; ; .

,

= ,

, () () BuildTree 0 , () () Optimize . , BuildSolution ( ) 0 0 . , , : = ( ) , ( ) 1, (. 6). ,

(

)1

. 6.

,

0

BuildSolution.

5. Irreducible1 .
: , : u 2 . :
0

.

ML-

261

B O B

u p u

i t i

l i l

d m d

T i S

r z o

ee( , 0 ); e( ); lution( , 0 ); ( ( )).

Irreducible1 , 0 Irreducible1 ( , , 0 ). 10, 12 13, BuildSolution Irreducible1 14. u = Irreducible1 ( , (3). , 0 )

DecoderA c A = Irreducible1 Decoder1 . 15. Decoder1 ( 2 ) , ( ) . . , + - 1. , H , ( ), . , BuildTree, Optimize BuildSolution , (. . 251) , . , , , + . Decoder1 , , c u, , , . , , ( ), . , , Decoder1 ( ) . Decoder1 ( ), . BuildTree, Optimize BuildSolution,

262

. .

. , , , ( Irreducible1 ), ( ), . , Decoder1 , . , , ( ), . , Decoder1 ( 2 ) . . 9, 14 15, 1. , (3) , , , , , c 0 c 7. , , 2. , .

5.

2

( , ). , , 2. , 0 . . , , , , , , . , , , . , -

ML-

263

, , . . + 1, + 2, . . . . . > , . 7 . , . , , ( , ). , , , , , , . ( )={ }, ( )={ }.

, , (. . 242). , , -, , -, . , 0 = { 0 }. (. 7 ). , , , , . a 2 a , , supp a. , a (. 7 ).

264

. .

, a. , a , . , 0 . , , , (3). 16. , 0 u 2 , u , 0 . . u 2 , , 0 . supp u = 2 ( ) 0 supp u = 1, u , 0 . , , c supp c supp u. , c, , , , . , , 0 . , supp c = 1. , c . u , 0 . , u , 0 u . u , u, , 10. u , u , . 0 (u) = 1 , 0 u . , u . u , . u , , 0 . u , supp u = ( ). u , supp u supp u. u , 0 . u = u , u = u c, c , c = 0. - u, u = u u = . .

ML-
1 4 1 1 4 5 4 2 3 2 2 6 3 5 2 6 5 3 3 6 1

265

1

1 1

4

1 5 4 5 8

4

2 2 2 6 3 5

2 6 9

7 3 6

1

a

a
1

4

1 4 4 2 2 6

1

7 3 9 6

6

3

. 7. (), = {1, 2} () a , a = (1 0 1 1 0 1) ().

266

. .

, , 0 . , (3). , 0 . , , c 0 c . ( , ) , . , a 2 , a a ( , ). 16 17. u (3) 0 2 , u ( , ), .

, (3) . , , . , 7, (3) . 18. ( , ) . . , c , c 0. , , . . , ( ) .

ML-

267

[14, 12.12]. , , , [14, . 11] ( 3 ). , , ( + 2 log ) [15]. 17 ( , ) , 0 . , , . = ( , , ), , : 2 , . , : , . , 0 , 0 . / 12.13 [14] 19. ( ShortestPaths), , 0 , , ( 3 ) . ShortestPaths , , 0 , ShortestPaths( , , 0 , ), : 2 , ( ) , , 0 , . , ( ) = . 6. BuildReduction .
: .

268
: : ; ( ,

. .

),

,

.

; = 2, ( ) ; = 1, + 1; { }; ( ) ( ) { }; = 0, + 1; + 2; ( ) { , }; ; ; ; ( , , ); ( , ).

{ , };

BuildReduction 20. ( , ) ( , , ), = ( , , ), , ( ) = ()= . , ( . = BuildReduction( ), = : : , ) :

( )= . ,

7. Irreducible2 .
: , : u 2 . : ( , ) BuildReduction( { 0 }); ShortestPaths( , , 0 , );
1

0

.

arg min

: ( ) = 2

()

;

u u.

, supp u = ( 1 );

ML-

269

21. Irreducible2 ( 3 ) , u = Irreducible2 ( , , 0 ) (3). . , ( , ) u ( ), . 19 ( 3 ), , 1 , , ( 2 ), . 17, 18, 19 20. DecoderA c A = Irreducible2 Decoder2 . 22. Decoder2 . (
4

)

. Decoder2 ( ), . , Decoder2 , Irreducible2 , . , , ( 3 ), . , Decoder2 ( 4 ) . . 9 , 2. - . , 2. (1) ( 3 ) . = ( , , ) : , , . : 2 , ( ) , , . , - , ( )

270

. .

, . - , , , . , , , . 12.11 [14] - , ( 3 ) . 23. 2, c 2 , c , c, -. . c -, supp c . , . . , (1) - , 24. , 2, , (1), ( 3 ) . 2, (1) - , . - . . ( ), ( 3 2 ( ) ) , , ( ) . Decoder2 .

ML-

271

[1] Berlekamp E. R., McEliece R. J., Van Tilb org H. C. A. On the inherent intractability of certain co ding problems // IEEE Trans. Inform. Theory. Vol. 24. 1978. P. 384386. [2] Bruck J., Naor M. The hardness of deco ding linear co des with preprocessing // IEEE Trans. Inform. Theory. Vol. 36. 1990. P. 381385. [3] Coffey J. T., Go o dman R. M. F., Farrell P. G. New approaches to reduced-complexity deco ding // Discr. Appl. Math. Vol. 33. 1991. P. 4360. [4] Hwang T. Deco ding linear blo ck co des for minimizing word error rate // IEEE Trans. Inform. Theory. Vol. 25. 1979. P. 733737. [5] Agrell E. Voronoi regions for binary linear blo ck co des // IEEE Trans. Inform. Theory. Vol. 42. 1996. P. 310316. [6] Massey J. L. Minimal co dewords and secret sharing // Pro c. of the 6th Joint Swedish-Russian International Workshop on Information Theory. Molle, Sweden, 1993. P. 246249. [7] Ashikhmin A., Barg A. Minimal vectors in linear co des and sharing of secrets // Pro c. of the 4th International Workshop on Algebraic and Combinatorial Co ding Theory. Novgoro d, 1994. P. 115. [8] Barg A. Minimum distance deco ding algorithms for linear co des // Pro c. of the 12th International Symp osium on Applied Algebra, Algebraic Algorithms and Error-Correcting Co des. Lecture Notes in Computer Science. Vol. 1255. 1997. P. 114. [9] Ashikhmin A., Barg A. Minimal vectors in linear co des // IEEE Trans. Inform. Theory. Vol. 44. 1998. P. 20102017. [10] Wib erg N. Co des and deco ding on general graphs / Ph. D. dissertation. Sweden: Linkoping Univ., 1996. [11] Lin S., Costello D. J. Error Control Co ding: Fundamentals and Applications, 2nd Edition. Upp er Saddle River, NJ: Pearson Education, 2004. [12] Mo on T. K. Error Correction Co ding: Mathematical Metho ds and Algorithms. Hob oken, NJ: Wiley, 2005.

272

. .

[13] Richardson T., Urbanke R. Mo dern Co ding Theory. NY: Cambridge University, 2008. [14] Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms, 4th Edition. Berlin: Springer-Verlag, 2008. [15] Gab ow H. N. Data structures for weighted matching and nearest common ancestors with linking // Pro c. of the 1st Annual ACMSIAM Symp osium on Discrete Algorithms. 1990. P. 434 443.