Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v14(1-4)/tsymzhitov-543-560.pdf
Дата изменения: Mon Jun 6 07:25:11 2011
Дата индексирования: Tue Oct 2 00:31:19 2012
Кодировка:

. .

ML- , max . , , . max , , . , (ln ) . . : , , , , .

1.
, ML- , . , , , - . , -

544

. .

, ML-. . , , , NP- [1]. , , [2]. , , . , , . , ( 200 ). , , [3, 4, 5, 6, 7, 8], [3]. ML- (. zero neighbors ), [9]. [4, 7, 10]. ML- , [11]. , , . [4, 7, 10, 12, 13, 14]. , , . , , -

545

[11]. , [11] , , . [10] , . , , , . , max . , , . , ML-. max , ( ), . , (ln ) . . , . , , . , max . , . . . ..-.. . . .

546

. .

2.
, , [15, . 1] [16, . 1 11]. . , 2 . ( ) , , 2 . 1 1 ( ) = exp - 2 ( - ~) 2 2
2

,

~ = (-1)

.

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

)=

1 1 ~ exp - 2 r - a2 , 2 ( 2)

~ ~ a = (~1 , . . . , ~ ) r - a ~ r a. (r a) , r , a 2 . , . r , c , . ,

547

, , . , , , MAP- (. maximum a posteriori decoding ). P(c r) , c , , r . MAP- r c , P(c r). , , c P(c) = -1 . , MAP- ML- (. maximum likelihood decoding ), (r c). r . r ^ = ( ^1 , . . . , ^ ) 2 , r ^= 0, 1, 0, < 0, = 1, . . . , .

, ^ , r , . r (r) = ( 1 , . . . , ) . ^. r + ( + ), (a, b) =
: =

(a) =
: =0

,

a, b

2

,

. ,

548

. .

. , , . , (r a) = (r ^) r
2 - (^,a) r

,

= (r),

( = 2 ). ML- (^, c) min, r (e) min, c , (1)

e = ^ - c r e^+ . r (2) , . [11] ( ), . c , . ( ). [11, 2]: e ^ + r (2) , (e) (e + c) c ( ). r . e0 = ^, r ^ + e1 , e2 , . . . r , e +1 = e + c +1 0, c +1 (e + c
+1

(r),

) min,

c

+1

( ).

549

(e ) e ^ + r , (e ) (e + c +1 ). , 0, (e ) (e + c +1 ). , (e0 ) > (e1 ) > . . . > (e ), e (2), c = ^ - e r (1). , , (1), (e + c) min, c ( ). (3)

OptimalDeco der, r OptimalDeco der(r). (. [11, 4]) c = OptimalDeco der(r) (1). , . r {^ - e } =1 , , , . . 1. ( ) A, + e 2 c = A( , e), (3). .
: max , r ; : c . 1) : (r); e ^; c A( , e); 0; r

550

. .

2) (e) > (e + c) e e + c; c A( , e); 3) (e) (e + c),

< max : + 1; c ^ - e; r .

1 LimitedDeco derA , max r LimitedDeco derA ( max , r). , ML-. , 0 < < 1. ( )= ( , , , ) = log
()

1

,

( )=

() . ( )-1
2

2

(0, 1) = 2 2 > 0. opt LimitedDeco derA . 1. (0, 1). max LimitedDeco derA , max ( , , , ), P(opt ) < 2P( ) + . 2. > 0 , (0, 1) ( , , , ) = (ln ) . , , > 0 > 0. , ML- .

-

1 - ln

1-

1-

2

+

ln(1 - 2 )

,

551

(0, 1) LimitedDeco derA max = ( , , , ) , , (1 - ) . , ML-, 1. , 2 max , (ln ) .

3.
^ = e0 , e1 , . . . , e r ^ + , e +1 = e + c +1 , c +1 r (e + c
+1

) min,

c

+1

( ), (e ),

0. , , (e0 ) > (e1 ) > . . . >

e ^ + , r (2). 3. , 0 , (e ) - (e ) ( )- ( (e0 ) - (e )).

. = 0 = . 1 < c = e - e -1 . c , . . . , c ( ) , 1 c = c + . . . + c . 1 , -, 1 ( ),

552 -, (e
=1 -1

. .

+ c ) -

(e

-1

)=
-1

(e

-1

+ c ) -

(e

-1

) < 0.

e = e (e
-1

+ c ^ + , r = 1, . . . , .

+ c ) -

(e

-1

) 0
0

, (e
-1

, (e
-1

+ c 0 ) -

(e

-1

)

(e ) -

)

(e ) - (e () )

-1

)

.

c = e - e (e ) , , (e ) (e ) + ( )-1 ( () ( )-1 () (e (e
-1

-1

, ,
-1

)+

(e ) - (e ()

-1

)-

(e )).

, , (e ) (e ) + ( (e0 ) - (e )).

. OptimalDeco der, . {^ - e } =1 , r , , . 2. ( ) A, + e 2 c = A( , e), (3). .

553

: max , r ; : c . 1) : (r); e ^; c A( , e); 0; r 2) (e) > (e + c) < max : e e + c; c A( , e); + 1; 3) c ^ - e. r

2 LimitedDeco der , A max r LimitedDeco der ( max , r). A , max , LimitedDeco der . A sub LimitedDeco der . A 4. 0 < < 1 r . max LimitedDeco der , A
max

log

()

-
sub

(^) r ln(1 - )

(^) > 0, r

. LimitedDeco der A max r, , ^ - e , 0 . = , r P(sub r) = P( r) < P( r) + . (^) = 0, = = 0. r , , (^) > 0 < . r , P( r) + < 1, , , . c = ^ - e c = ^ - e . r r P(c r) (r c ) 1 - P( r) = = = 1 - P(sub r) P(c r) (r c) = exp{- (^, c ) + r (^, c)} = exp{ ( r exp{
-

P(

r) < P( r) + .

(

(^) - r

(e ))} exp{

(e ) -

-

(e ))}

(^)}. r

554

. .

= ( ), 3. 1 P( r) P( 1 - P( r) exp{ 1 - P(sub r) r) 1 - exp{-
- - -

(^)}, r (^)} (1 - P( r)) . r (4)

sub

1 - exp{-

(^)} (1 - P( r)) - P( r) < . r (5)

exp{-
-

(^)} > 1 - r

1 - P( r)

.

, log

, P( r) + < 1, , , , - ln 1 - 1-P( r) - < . (^) r > 1 , , , (^) r . > log - ln 1 - 1-P( r) (^) r
1-P( r)

- ln 1 -

< , e , LimitedDeco der , A . =
max

< log

-

(^) r ln(1 - )

.

log

-

(^) r ln(1 - )

,

555

(5) . (4) . 5. 0 < < 1. r max LimitedDeco derA ,
max

log

()

-
sub

(^) r ln(1 - )

(^) > 0, r

P(

) < P( ) + .

. 4 r P(sub r) < P( r) + . P(
sub

)=

P(

sub

r) (r) r <

<

P( r) (r) r +

(r) r = P( ) + .

, LimitedDeco der A ^, r. r 6. 0 < < 1. max LimitedDeco der , max A ( , , , ), P(
sub

) < P( ) + . >

. = { v , 1 }.
max

2+

log

()

-

ln(1 - 2 ) (^) r

,

(6)

r

P(
sub

( 4)

r) < P( r) + /2.

556 , P(
sub

. .

)=

P(

sub

r) (r) r + P( 2

sub

)P( ) < 2 + P( ),

<

P( r) (r) r +

(r) r + P( ) = P( ) +

= . , P( ), P( ). P( ) = (r) r = 1 = 1
c

(r c) r = 1 1 exp - 2 r - ~2 c 2 ( 2) r.

c

0 c

= {v = {v
c

-

-~

,1 } - , 1 } c . r= r=

1

c
c
c

P( ) >

1 1 ~ exp - 2 r - c2 2 ( 2) 1 1 exp - 2 r2 2 ( 2) r= =

=

1 =
c
0

= ( )

-

0

1 1 exp - 2 r2 2 ( 2)
2 2

-+

1 1 exp - 2 2

- 2

,

. , - P( ) = 1 - P( ) < 1 - 2

.

557

> 1
+ -
2

2 ( ) = 1 - (

2 >1- )

+

-

2 =1-

-

,

>

2+

P( ) < 1 - 1- - 2 ln

2 - 1 - exp - 2 , 2

.

- 2 1 - exp - 2 2

1-

1-

2

+

.

(7)

2+ , (6) (7) , > , P( ) < /2 P(sub ) < P( ) + . , , = 2 1 - ln 1- 1- + 2 2
max

log

()

-

.

ln(1 - 2 )

= ( , , , ).

. 1. , max LimitedDeco derA LimitedDeco der A opt , LimitedDeco der A . ,

558

. .

LimitedDeco der , A = sub . LimitedDeco der , A , . P(opt ) P() = P(
sub

) P( ) + P(

sub

) < 2P( ) + ,

6. 2. ( 2 + log

= ( ))
2

( , , , ) = log

1 - ln

2

1-

1-

+

- ln(1 - 2 )

.

, , , = 1 - 2 . , - ln 1 - 1/ < 0 ln < ln 0 < 0. 0 = 1 - 3 , = 1 + ln + ( ) 0, 1 + ln 0 > > 0. , - ln 1 -
1/

< - ln 1 - 1 + +

1

ln

0

= ln

- ln

.
0

( , , , ) = log

(ln ln ) =

(ln )

.

[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] Prange E. The use of information sets in deco ding cyclic co des // IRE Trans. Inform. Theory. Vol. 8. 1962. P. 59.

559

[4] Barg A. Minimum distance deco ding algorithms for linear co des // in 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. [5] Barg A., Krouk E., Van Tilb org H. C. A. On the complexity of minimum distance deco ding of long linear co des // IEEE Trans. Inform. Theory. Vol. 45. 1999. P. 13921405. [6] Coffey J. T., Go o dman R. M. F. The complexity of information set decoding // IEEE Trans. Inform. Theory. Vol. 36. 1990. P. 10311037. [7] 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. [8] . . // . . . 25. 1989. . 103107. [9] Levitin L. B., Hartmann C. R. P. A new approach to the general minimum distance deco ding problem: the zero-neighb ors algorithm // IEEE Trans. Inform. Theory. Vol. 31. 1985. P. 378384. [10] Ashikhmin A., Barg A. Minimal vectors in linear co des // IEEE Trans. Inform. Theory. Vol. 44. 1998. P. 20102017. [11] Hwang T. Deco ding linear blo ck co des for minimizing word error rate // IEEE Trans. Inform. Theory. Vol. 25. 1979. P. 733737. [12] Borissov Y. Minimal/nonminimal co dewords in the second order binary Reed-Muller co des: revisited // in Pro c. of the 11th International Workshop on Algebraic and Combinatorial Co ding Theory. Pamp orovo, Bulgaria, 2008. P. 2934. [13] Borissov Y., Manev N., Nikova S. On the non-minimal co dewords in binary Reed-Muller co des // Discr. Appl. Math. Vol. 128. 2003. P. 6574. [14] . ., . . // . . . 34. 1998. . 3746.

560

. .

[15] Lin S., Costello D. J. Error Control Co ding: Fundamentals and Applications. Englewo o d Cliffs, NJ: Prentice-Hall, 1983. [16] Mo on T. K. Error Correction Co ding: Mathematical Metho ds and Algorithms. Hob oken, NJ: Wiley, 2005.