`
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`____________________
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`_____________________
`
`LG Electronics, Inc.
`Petitioner,
`
`v.
`FastVDO LLC
`Patent Owner.
`
`
`Patent No. 5,850,482
`_______________________
`
`Inter Parte Review No. ____________
`
`___________________________________________________________
`
`K. Fazel et al., Application of Unequal Error Protection Codes on Combined
`Source-Channel Coding of Images, International Conference on
`Communications, Including SuperComm Technical Sessions (IEEE), Atlanta,
`April 15 19, 1990, Vol. 3, pp. 898-903
`
`Exhibit 1005
`
`

`

`APPLICATION OF UNEQUALERROR PROTECTION CODES
`ON COMBINED SOURCE-CHANNEL CODING OF
`IMAGES
`
`K . FAZEL - J.J. LHUILLIER
`
`LABORATOIRES D'ELECTRONIQUE PHILIPS
`3, avenue Descartes, 94450 Limeil-BrBvannes, France
`
`ABSTRACT
`
`combined
`i n v e s t i g a t e s a
`This paper
`source-channel encoding o f
`images w i t h a small
`amount o f redundancy. The source encoder under
`the Discrete-Cosine-Transform
`study
`i s based on
`(DCT), adaptive q u a n t i z a t i o n and v a r i a b l e l e n g t h
`(VLC) ; w h i l e
`the channel encoder
`i s
`encoding
`the unequal error p r o t e c t i o n
`(UEP)
`based on
`p r i n c i p l e . To measure the importance o f each b i t
`i n the transmitted frame a f t e r t h e VLC, a f a c t o r
`o f s e n s i t i v i t y f o r each b i t t o channel e r r o r s i s
`defined. By u t i l i z i n g t h e f a c t o r o f s e n s i t i v i t y ,
`the optimal e r r o r r a t e allowed f o r each b i t i n the
`frame,
`t h a t minimizes
`the e f f e c t s o f channel
`two UEP
`noise,
`i s estimated. The performance o f
`codes
`constructed by
`t h e Blokh-Zyablov
`code
`c o n s t r u c t i o n method,
`are evaluated
`f o r
`two
`sequences o f images.
`
`INTRODUCTION
`redundancy o f d i g i t a l TV
`t h e
`reduce
`To
`images,
`d i f f e r e n t coding algorithms have been
`studied. The performance o f such an algorithm
`depends mainly on i t s compression f a c t o r and the
`s i g n a l t o noise power r a t i o (SNH) a t t h e decoder
`side. The higher
`the compression
`f a c t o r a t
`the
`source,
`the greater
`i s the s i g n i f i c a n c e of
`the
`transmitted information, and hence the greater t h e
`e f f e c t s o f channel e r r o r s . The v i s i b i l i t y o f
`channel e r r o r s depends s t r o n g l y on
`t h e source
`encoding algorithms. As an example the minimum b i t
`e r r o r r a t e (BER) f o r which e r r o r s are j u s t n o t i c e -
`f o r a simple DPCh
`able a t
`the display
`i s 10-7
`algorithm ( f i x e d l e n g t h codewords) ; whereas i t
`f a l l s dbwn t o 10-10 when t h i s a l g o r i t h m i s f o l l o w -
`ed by variable-length-encoding
`(VLC) [ 1 ].
`As a r e s u l t ,
`f o r noisy channels applications,
`i t i s necessary t o c o r r e c t the channel errors or
`t o devise methods
`f o r
`reducing
`t h e e f f e c t o f
`
`e r r o r s (techniques o f error-concealment) . I n the
`
`f i e l d o f e r r o r c o n t r o l many coding techniques have
`been studied. These techniques consist o f coding
`the
`images without
`t a k i n g
`i n t o account
`t h e i r
`c h a r a c t e r i s t i c s , or, on
`the contrary, combining
`the source and channel coding by u t i l i z i n g the
`p r o p e r t i e s o f images.
`I n t h i s l a s t case many tech-
`niques have been i n v e s t i g a t e d h-31. Modestino e t
`a1 [Z] use the p r i n c i p l e o f f i n d i n g a t r a d e - o f f
`between source and channel coding, when the source
`encoder under study
`i s based on
`the d i s c r e t e -
`cosine-transform (LET), and a f i x e d number o f b i t s
`a l l o c a t e d t o each transformed block (no VLC). By
`applying c o n v o l u t i o n a l and block codes ( a l l w i t h
`low coding r a t e ) ,
`they consider three d i f f e r e n t
`
`( i n f o r m a t i o n b i t s
`s e l e c t i v e p r o t e c t i o n options
`the DCT c o e f f i c i e n t s are
`which are r e l a t e d t o
`coded i n three d i f f e r e n t ways) f o r a l a r g e s e t o f
`encoder
`and decoder
`p a i r s . Using
`the
`same
`[3] by estimating
`p r i n c i p l e , Gomstock and Gibson
`the more important b i t s o f the DCT blocks t o be
`protected,
`evaluate
`t h e performance of
`some
`Hamming codes. Since these techniques consume a
`p a r t o f
`the a v a i l a b l e b i t r a t e as p a r i t y check
`b i t s f o r the more important c o e f f i c i e n t s o f
`the
`DCT block, a performance degradation i s expected.
`However
`t h i s performance degradation
`i s much
`smaller than the one expected i f no p r o t e c t i o n is
`performed (when e r r o r s occur).
`The purpose o f t h i s paper i s t o i n v e s t i -
`( < 11 %), where t h e
`gate combined source-channel encoding w i t h a small
`amount o f e x t r a redundancy
`adaptive
`the DCT,
`source encoder
`i s based on
`l e n g t h encoding. The
`q u a n t i z a t i o n and v a r i a b l e
`channel encoder
`i s based on
`the unequal-error-
`p r o t e c t i o n (U.E.P)
`codes, where only one encoder-
`decoder i s r e q u i r e d t o achieve d i f f e r e n t l e v e l s o f
`p r o t e c t i o n i n the transmission message word. The
`main
`important
`f u n c t i o n s o f
`t h e source encoder
`under study,
`t h e i n f l u e n c e o f channel e r r o r s on
`the p i c t u r e q u a l i t y and
`the e r r o r s e n s i t i v i t y
`f a c t o r o f each b i t (i.e.the measure o f importance
`o f each b i t ) i n the v a r i a b l e l e n g t h coded frames
`( i . e . DCT block c o e f f i c i e n t s coded i n VLC), are
`i n s e c t i o n 11. The optimal b i t e r r o r
`described
`r a t e s (i.e.
`t h e optimal e r r o r - p r o t e c t i o n
`l e v e l s )
`required f o r each b i t i n t h e transmitted frame i s
`discussed i n s e c t i o n Ill. I n s e c t i o n I V by review-
`i n g b r i e f l y t h e U.E:P.
`codes and an
`i n t e r e s t i n g
`way of c o n s t r u c t i n g them, Blokh-Zyablov (bZ) code
`construction,
`we
`bring-out
`some
`c o n s t r a i n t s
`imposed by
`the c h a r a c t e r i s t i c s o f
`the source
`encoder frames (i.e.
`frames w i t h v a r i a b l e length,
`and
`good synchronization p r o p e r t i e s ) . F i n a l l y
`examples and numerical
`r e s u l t s are given and
`discussed i n s e c t i o n V. P a r t i c u l a r a t t e n t i o n i s
`p a i d
`t o
`t h e number o f
`l e v e l s o f p r o t e c t i o n
`r e q u i r e d f o r the U.E.P.
`codes
`t o a t t a i n optimal
`performances.
`
`11. SOURCE CODING ALGORITHM AND INFLUENCE OF
`TRANShISSION ERRORS
`a ) Source coding algorithm
`To
`reduce
`the raw b i t r a t e o f d i g i t a l
`d i f f e r e n t coding algorithms have been
`images,
`studied. For
`l i m i t e d bandwidth channels,
`t h e
`performance measurement of such a coding scheme
`depends on
`i t s compression f a c t o r ,
`the s i g n a l t o
`noise power r a t i o (SNR) a t the decoder side and
`
`0898
`
`320.5.1.
`CH2829-0/90/0000-0898 $1 .OO 0 1990 IEEE
`
`Apple Inc. Exhibit 1005 Page 1
`
`

`

`reconstructed
`the
`the s u b j e c t i v e q u a l i t y o f
`p i c t u r e (a reasonable SNR
`i s n o t on i t s own a
`guarantee o f good p i c t u r e q u a l i t y ) .
`One of
`the most a t t r a c t i v e schemes pos-
`sessing a h i g h performance i s based on t h e Dis-
`(DCT) 141, whose block
`crete-Cosine-Transform
`diagram i s given i n f i g . 1. L e t ’ s b r i e f l y look
`- the p i c t u r e i s d i v i d e d i n t o small blocks o f
`a t the more important functions o f t h i s scheme:
`the DCT. Let f ( j , k ) j, k = 0 ,.., n-1 denote
`
`(NxN) p i x e l s , and each block i s submitted t o
`
`the amplitudes o f the p i x e l s before t r a n s f o r -
`mation. The bidimensional DCT i s then defined
`F(u,v)= 4c(u)c(v) 1 1
`( 2 ‘+l)ulT
`by :
`f ( j , k ) cos{ ‘IzN }
`j k=O,. .N-1
`N-1, and C(w) = 4%
`
`u,v = O,..
`
`for w = 0
`L 1 elsewhere
`these transformed samples are quantized. The
`quantization step v a r i e s according
`t o
`t h e
`a c t i v i t y o f the block and t o the frequency,
`i n order t o l
`i m i t t h e v i s i b l i t y o f the coding
`noise ;
`(except DC
`the quantized values
`f i n a l l y
`component F(0, 0 ) ) are coded using variable-
`length-coding t o minimize t h e output b i t r a t e
`without l o s s o f information. As
`t h i s process
`generates a v a r i a b l e output b i t r a t e , a
`b u f f e r memory i s incorporated, combined w i t h
`a
`r e g u l a t i o n mechanism,
`r e a c t i n g on
`t h e
`quantizer,
`t o match
`the
`f i x e d b i t
`r a t e
`requirement o f the channel.
`t h e
`To
`f u r t h e r
`improve
`t h e e f f i c i e n c y o f
`scheme,
`one can perform
`t h e s t a t i s t i c a l
`coding
`(VLC) on several adjacent blocks
`multiplexed on a c o e f f i c i e n t basis. Thus
`s p a t i a l c o r r e l a t i o n can be taken i n t o account
`t o reduce the number o f b i t s devoted t o the
`DC components. The b i t stream i s obtained by
`4 adjacent blocks ( 1 quad-
`combining
`block)
`i n the f o l l o w i n g way
`( f i g . 2a) : 9
`b i t s which are reserved f o r t h e DC component
`o f the f i r s t block, 4 x 2 b i t s f o r the a c t i -
`followed by
`t h e d i f f e -
`v i t i e s o f 4 blocks,
`the remaining DC components
`rences between
`the 1 s t DC component, and completed by
`and
`the variable-length codewords corresponding
`t o
`the other c o e f f i c i e n t s o f
`the blocks
`previously scanned
`i n a zig-zag order and
`multiplexed. Because
`t h i s frame contains a
`v a r i a b l e number o f values
`(zeros are
`r u n
`l e n g t h coded), 8 s p e c i a l separation p a t t e r n
`(End O f Block = EOB) belonging t o the Huffman
`t a b l e i s inserted.
`This coding algorithm achieves a h i g h
`performance f o r various sequences o f image.
`I n t h e absence o f channel errors,
`t h e SNR i s
`greater than 34 dB
`f o r a b i t r a t e o f 1 b i t /
`p i x e l . L e t ’ s look a t t h e performances degra-
`d a t i o n o f t h i s a l g o r i t h m i n the presence o f
`channel e r r o r s i n the next sections.
`b ) Influence of channel errors
`t h e
`As was mentioned i n the i n t r o d u c t i o n ,
`higher the compression f a c t o r ,
`the greater the
`s i g n i f i c a n c e o f t h e t r a n s m i t t e d i n f o r m a t i o n and
`hence t h e greater the e f f e c t s o f errors.
`
`-
`
`-
`
`I n p r a c t i c e , channel e r r o r s cause more
`degradation than
`the b i t r a t e reduction.
`I n
`a d d i t i o n v i s i b i l i t y of channel e r r o r s depends
`s t r o n g l y on the source encoder algorithm. For
`t h e encoder under study, by t a k i n g t h e ELIB as
`t h e synchronization pattern, we can p o i n t out
`the f o l l o w i n g events i n t h e presence o f channel
`e r r o r s :
`I f the e r r o r s occur i n t h e f i x e d l e n g t h p a r t of
`the frame,
`the v i s i b i l i t y o f the corresponding
`defects i s p r o p o r t i o n a l t o the s i g n i f i c a n c e o f
`the corrupted
`i n f o r m a t i o n
`( f o r
`instance an
`error i n the most s i g n i f i c a n t b i t s o f the DC
`component would dramatically modify the whole
`block).
`I f the e r r o r s occur i n the v a r i a b l e l e n g t h p a r t
`o f
`the stream a c o r r e c t segmentation
`i s no
`longer garanteed. It may be
`recovered i f a
`self-synchronization code [ 5 ] i s used, b u t i t
`doesn’t prevent from merging 2 frames (or more
`if the synchronization p a t t e r n s themselves are
`wrong)
`i n t o one. I t induces some s p a t i a l s h i f t
`t h a t i s unacceptable from a s u b j e c t i v e p o i n t o f
`l
`l
`view. To solve t h e problem, a new framing w i
`be discussed i n s e c t i o n I V .
`the
`Assuming a good synchronization,
`importance o f each b i t i n the transmitted frames
`can be quantized by
`i t s s e n s i t i v i t y
`t o channel
`e r r o r s .
`c ) Error sensitivity of each bit
`The approach described here t o measure
`the s e n s i t i v i t y o f each b i t t o the channel
`e r r o r s
`i s s i m i l a r
`t o
`the
`i n t u i t i v e approach
`which has been developed by 2. Hagenaurer e t
`[6 1.
`I t takes b e n e f i t o f
`the
`f o l l o w i n g
`a1
`remark : each b i t o f the b i t stream has t o be
`p r o t e c t e d proportionnaly
`t o i t s i n f l u e n c e on
`the SlvR when corrupted by an e r r o r . Levels o f
`p r o t e c t i o n and hence e r r o r p r o b a b i l i t i e s o f t h e
`t h a t
`t h e i r
`respective
`b i t s are adjusted so
`c o n t r i b u t i o n ( s e n s i t i v i t y ) t o the o v e r a l l noise
`power, weighted by
`t h e i r e r r o r p r o b a b i l i t i e s ,
`are equal. This c o n d i t i o n leads t o an optimal
`s e t o f parameters.
`t h e SlvR
`f o r a given
`More precisely,
`i s
`i n the presence o f channel e r r o r s
`image
`given by : SlvR = 10 l o g
`
`defined as the t h e o r e t i c a l
`.PN
`represents
`image and
`Then P
`i s given by :
`N
`
`t h e noise power.
`
`noise.
`
`M
`4N2
`PN = c
`- ki(kIe)’
`i=l k = l (xi(k)
`Where M and (\r2 are r e s p e c t i v e l y t h e number o f
`quadblock ( 4 adjacent blocks) i n the image and
`t h e number o f p i x e l s i n each block.
`Where xi( k ) represents the kth p i x e l amplitude
`o f t h e ith block before encodin and F i ( k ) e the
`i # h block a f t e r
`k t h p i x e l amplitude o f
`the
`i n the presence o f channel e r r o r s . I f
`decoding,
`there i s np. channel e r r o r x^’(k)e = ^xl(k) and^
`( i l ( k ) , - x l ( k ) )
`represents the source coding
`L e t li be t h e l e n g t h o f coded frame +,
`l be 211.
`
`then the number o f e r r o r p a t t e r n s w i
`
`l
`
`320.5.2.
`
`0899
`
`Apple Inc. Exhibit 1005 Page 2
`
`

`

`independence of e r r o r p a t t e r n s from
`Assuming
`frame t o frame,
`the noise power can be expres-
`sed as *
`M 4'N2
`M 21i
`C Pe
`C E (k,i) + C
`, C
`1=1 k=l
`i=l e=l
`
`x
`
`PN
`
`4NL
`(kzl E;(k,i)+2
`where :
`
`(k,i)
`
`EC(k,i)X E (k,i))
`q
`xi(k) - Pi(k)
`A1(k) - Pi(k)
`tehe e t h error
`i s the p r o b a b i l i t y o f
`
`ano Pe
`pattern.
`The pN can be w r i t t e n as :
`
`where :
`
`. .
`.
`2
`C E
`= C
`P
`i=l k=l
`nq
`which i s the source coding noise.
`21i
`M
`
`(k,i),
`
`A i = :!$; ~ ~ ( k , i j + 2
`2
`~ ~ ( k , i ) x E (k,i)
`
`9
`P
`depends on
`the channel errors, and i t
`cbk be considered as the sum o f channel noise
`and
`the
`i n t e r a c t i o n o f source coding-channel
`noises.
`Assuming t h a t we can neglect the e f f e c t o f
`e r r o r p a t t e r n s o f weight > 1 a f t e r correction,
`then PNc can be w r i t t e n as :
`M
`li
`- C
`P . A!
`C
`P
`
`J
`J
`NC - i=l j=1
`where P j i s the p r o b a b i l i t y o f e r r o r i n the jth
`b i t (Pj. doesn't depend on the frame) and A l
`j i s
`t o an e r r o r on b i t J o f
`the noise power due
`block i.
`p..- can be r e w r i t t e n as :
`h a x
`NL 1
`M
`C p . A_
`Cmax p . . C A 1
`( 1 )
`
`j=1 J
`J
`'NC - ,j=1
`j 1=i J
`
`Wheh lmaX i s the maximal
`frame-length value
`and A;
`the averaae c o n t r i b u t i o n o f an e r r o r on
`b i t j J o n any block.
`From previous formula (I), the s e n s i t i v i t y o f
`b i t j can be derived :
`
`(SNR) .
`J
`
`j = 1, ...
`
`?llElX
`
`'SM
`10 l o g
`+ A .
`~ P
`J
`Nq
`t h a t i s obtained by systematicaly p u t t i n g an
`e r r o r a t the j t h b i t p o s i t i o n o f a l l frames.
`A curve o f s e n s i t i v i t y has been p l o t t e d
`f o r " G i r l " TV sequences i n f i g . 4
`t h a t i s i n
`agreement with
`expectations
`o f
`previous
`section. Optimal s e t o f b i t e r r o r r a t e s P j i s
`evaluated i n the next section.
`
`111. OPTIMAL B I T ERROR RATE REQUIRED FOR EACH B I T
`t THE T R A m l t D tRAMt
`the SNR o f an
`As was discussed before,
`image,
`i n the presence o f e r r o r s depends s t r o n g l y
`on the b i t e r r o r r a t e f o r each b i t . To determine
`the optimal BER f o r each b i t t h a t achieves a h i g h
`SNR, i t i s d e s i r a b l e t o f u l f i l the f o l l o w i n g con-
`d i t i o n : P N C = K < < P , where P
`i s the channel
`
`noise and p
`i s t h e source coding noise.
`We
`cakq choose a s e t o f P j SO
`t h a t a l l
`c o n t r i b u t i o n t o noise power are equal. This choice
`d r i v e n by
`i n t u i t i o n i s proved
`t o minimize a
`c r i t e r i o n
`s t r o n g l y
`r e l a t e d
`t o
`the
`o v e r a l l
`P j K j = K , j 1, ... lmax I t y i e l d s : PNc = lmaX
`redundancy.
`
`p . = K ' ; K ' = -
`K
`o r
`A .
`lmax
`J
`where K i s a predefined constant.
`So t o respect t h e above condition, we have t o
`equalize the curve o f s e n s i t i v i t y factor. L e t ' s
`the b i t e r r o r r a t e
`consider the example o f " G i r l " ,
`i n f i g . 6. It
`r e q u i r e d f o r each b i t i s given
`corroborates our
`f i e l i n g
`t h a t
`the
`f i r s t b i t s
`(corresponding t o low order DCT c o e f f i c i e n t s ) need
`more p r o t e c t i o n than the l a s t b i t s (corresponding
`t o high order DCT c o e f f i c i e n t s ) . Although,
`i n case
`o f e r r o r , segmentation i s no longer c o r r e c t u n t i l
`the end o f
`the
`frame,
`the
`l a s t b i t s do not
`c o n t r i b u t e a l o t e i t h e r t o s i g n a l t o noise r a t i o
`o r t o s u b j e c t i v e q u a l i t y ( t h e human eye i s l e s s
`s e n s i t i v e t o h i g h frequency p a r t ) .
`
`I V . APPLICATION OF U.E.P. CODES
`a) Unequal-error-protection codes
`I n many a o o l i c a t i o n s i t i s desirable t o
`provide d i f f e r e n t p i d t e c t i o n l e v e l s f o r d i f f e r e n t s
`components m i o f the message word m. Linear codes
`t h a t provide a greater amount o f p r o t e c t i o n f o r
`c e r t a i n p o s i t i o n s
`than
`f o r others are c a l l e d
`unequal-error-protection codes [7-11 1
`A s u i t a b l e measure o f these protection-
`l e v e l s f o r d i f f e r e n t p o s i t i o n s i n a message word
`i s t h e so c a l l e d separation-vector [8 ] :
`the
`D e f i n i t i o n : For a l i n e a r (n,k) code C over
`(S(G)l, S(G)2 ... S(G)k) w i t h respect t o a genera-
`t h e separation vector S(G) =
`alphabet GF(q),
`m i # O } , i = 1, ... k
`t o r matrix G o f C i s defined by
`S(G)i = min {wt(mG)/mGGF(q)k,
`) denotes t h e Hamming weight function.
`where w t (
`V i , j = 1, K,
`If S ( G ) i = S ( G ) j
`then,
`the
`code i s an equal-error-protection.
`min (S(G) i), i = 1, ... k:
`The minimum distance o f the code i s dmin
`
`The e r r o r - c o r r e c t i o n c a p a b i l i t y o f a code,
`when we use a q-ary symmetric channel i s given by
`Theorem 1 [ 9 1: A
`l i n e a r code C over GF(q), with
`generator matrix G and complete maximum l i k e l i h o o d
`decoding, guarantees t h e c o r r e c t i n t e r p r e t a t i o n o f
`weight i s l e s s or equal t o sfc)i-1 .
`the ith message d i g i t , wheneve
`the e r r o r p a t t e r n
`
`code
`A basic problem i s t o f i n d an U.E.P.
`with a given dimension and separation vector such
`t h a t i t s information r a t e i s maximal. D i f f e r e n t
`construction methods have been studied [9 3 [U 1.
`i n t e r e s t i n g one i s based on
`the Blokh-Zyablov
`An
`(BZ) construction [111 We w i
` now examine t h i s
`l
`l
`c o n s t r u c t i n a method :
`B-lokh- Zyabiov (BZ) U.E.P.
`( f i g . 2b)
`
`code construction [U]
`
`L e t B i be a (n, k i , d i ) l i n e a r code over
`( 2 a i ) , with a generator matrix G i and minimum
`GF
`f o r i = 1, ..r L e t G be
`distance d i ,
`generator
`( m l , m2, ... mr), mie GF
`1!bi, ai, and
`matrix f o r a C(N, K ) code, where K
`l e t m =
`(2a1) 1 be the
`i t h components o f
`the message m.
`Then
`the BZ
`coding process i s as f o l l o w s :
`
`0900
`
`320.5.3.
`
`Apple Inc. Exhibit 1005 Page 3
`
`

`

`- t h e m i , i = 1.. .r, i s coded by the code B i : C i
`= m i G i p
`- then C i i s arranged i n the ith block ( a i l i n e s
`and n columns) of nxK m a t r i x M
`where each
`column of ith block i s the b i n a r y representation
`- f i n a l l y t h e complete m a t r i x h i s coded by G and
`o f symbols o f C i ,
`gives the BZ codewords : C = GTM,
`The r e s u l t i n g code i s a two dimensional (N,
`n) code o f l e n g t h nN and
`r
`r a t e R = HZlaiki.
`L e t e i n K ( i = 1, ... r ) denote
`
`the minimum
`distance o f the b i n a r y code generated by t h e l a s t
`( r - i + l ) blocks o f L,
`then the U.E.P.
`c a p a b i l i t y o f
`the BZ code i s derived i n t h e f o l l o w i n g :
`[U]. The BZ code has a separation
`Theorem 2
`. .mr)
`vector (S1,Sp,..Sr)
`f o r the message space (ml,m2,
`t h a t s a t i s f i e s the f o l l o w i n g i n e q u a l i t i e s :
`S i 2 ei.di
`i f d1.d 2 d2.e2 2 dr.er
`From t h e above construction, we can d e r i v e
`codes for a given dimension and
`d i f f e r e n t U.E.P.
`given code
`rate. L e t ' s see
`the a p p l i c a t i o n o f
`these codes t o imaqe transmission :
`b ) Application o f U.E.P.
`t o image transmission
`the
`As we saw before the b i t stream a f t e r
`source encoder has d i f f e r e n t l e v e l s o f s e n s i t i v i t y
`t o errors, hence an U.E.P.
`code i s required. The
`two problems encountered
`i n the a p p l i c a t i o n o f
`these codes can be s t a t e d as follows:
`
`- The l e n g t h o f each frame li varies,
`t h e
`thus,
`code should be adapted t o each li i.e.
`U.L.P.
`v a r i a b l e l e n g t h U.E.P.
`codes should be envi-
`- and f i n a l l y ,
`saged,
`
`f i n d an U.E.P.
`i f we
`t a k i n g
`code,
`then,
`i n t o account the above mentioned problem,
`l
`l be
`t h e data r a t e a f t e r t h e coding process w i
`variable, (
`redundancy v a r i e s with
`the added
`respect t o l i ) hence, i t has t o be regulated.
`codes - t h a t o f shortening
`The v a r i a b i l i t y o f the frame l e n g t h imposes a
`c o n s t r a i n t on U.E.P.
`the codewords i f li< number o f i n f o r m a t i o n b i t s
`available. A code can be shortened i f i t i s a
`systematic code. One systematic U.E.P.
`code can be
`designed by the BZ code c o n s t r u c t i o n i f t h e B i i s
`a systematic code and G has the f o l l o w i n g form :
`= 2
`8 1 here e l = 1, e2
`e3...er
`a2 and I i s t h e a1 x a1 i d e n t i f y
`ay m a t r i x
`
`' ]
`
`G = f
`
`1
`
`0
`
`1
`
`
`
`the
`the c l a s s o f code possessing
`However
`above p r o p e r t i e s i s l i m i t e d and does n o t have
`optimal performance, nevertheless i t solves
`the
`problem o f frame-length v a r i a b i l i t y and has a very
`simple decoding process.
`To r e g u l a t e the data rate, one can use the
`same p r i n c i p l e as used f o r r e g u l a t i n g t h e informa-
`t i o n data r a t e a f t e r the source encoder
`i.e.
`t o
`incorporate a supplementary b u f f e r memory, combin-
`ed with a r e g u l a t i o n mechanism r e a c t i n g on
`t h e
`U.E.P
`code. But the system complexity ( f o r encod-
`i n g and decoding) p r o h i b i t s such a s o l u t i o n . An
`a l t e r n a t i v e s o l u t i o n c o n s i s t s o f u s i n g a common
`b u f f e r memory ( f i g . 3)
`f o r source-channel enco-
`ders. The feedback w i
`l
`l be t h e same as the source
`
`encoder (i.e. c o n t r o l l i n g t h e q u a n t i z a t i o n step).
`As mentioned i n s e c t i o n 11, t h e synchronisa-
`t i o n between frames have t o be a b s o l u t l y guarante-
`ed
`t o avoid any s p a t i a l s h i f t i n t h e p i c t u r e .
`coding process modifies the VLC
`Since the U.E.P.
`data stream t h e u t i l i z a t i o n o f EOB (a VLC word) as
`t h e synchronization pattern, doesn't allow
`t o
`assure a synchronization between frames. To aver-
`come t h i s problem,
`t h e s o l u t i o n proposed here i s
`l e n g t h li i n order
`t o
`transmit
`the
`frame
`t o
`separate t h e frames. To increase robustness o f the
`t h i s frame lengths are also protected so
`system,
`t h a t synchronisation recovery i s h i g h l y improved
`f o r c r i t i c a l channel BER values.
`I t has t o be
`noted
`t h a t an
`i n i m i t a b l e p a t t e r n
`i s r e g u l a r l y
`i m i t
`t o l
`i n s e r t e d
`(between each 16 quad-block)
`error propagation.
`To i l l u s t r a t e t h e a p p l i c a t i o n o f these codes
`t o some sequences o f images, we w i
`l
`l give some
`examples and dicuss t h e s i m u l a t i o n r e s u l t s i n t h e
`following.
`V. EXAMPLES AND SIMULATION RESULTS
`t h e
`ction,
`
`
`N
`t
`r
`o
`t
`h
`e
`u
`purpose o f
`t h i s study
`i s t o define a combined
`source-channel encoding
`( w i t h small amount o f
`e x t r a redundancy), and t o i n v e s t i g a t e the p e r f o r -
`codes i n t h e case o f random e r r o r 8
`mance o f U.E.P.
`(Binary Symmetric Channel : BSC). TWQ sequences o f
`images : " G i r l " and Y3altimore" are coded w i t h t h e
`source-encoaer described i n s e c t i o n I1 (block s i z e
`6x8 ; b i t r a t e 1 b i t / p i x e l ) . The error s e n s i t i v i t y
`f a c t o r o f each b i t i n t h e coded variable-length
`frame
`i s measured
`f o r each sequence and
`i s
`represented i n Fig. 4. These curves have approxi-
`the SNR
`mately
`the same shape and show
`t h a t
`depends s t r o n g l y on t h e p o s i t i o n o f erroneous b i t s
`i n t h e t r a n s m i t t e d frames.
`The s e t of Pj i s c a l c u l a t e d as i n d i c a t e d i n
`s e c t i o n 111 f o r a constant K equal t o 10-5. The
`e r r o r s e n s i t i v i t y f a c t o r s reordered i n an increas-
`the optimal error r a t e f o r
`i n g manner ( f i g . 5),
`i n Fig. 6. As shown by
`each b i t i s represented
`these curves, t h e f i r s t b i t s o f each ordered frame
`have
`t o be protected
`t o give an e r r o r r a t e of
`around 10-9, w h i l e t h e l a s t ones dodt r e q u i r e any
`p r o t e c t i o n , i f the channel b i t e r r o r r a t e i s l e s s
`than 10-2. Hence d i f f e r e n t l e v e l s o f p r o t e c t i o n
`are required.
`The frame-lenyth, which i s t h e most important
`information, has
`t o be protected very e f f i c i e n -
`t l y . Four frame-lengths a r e gathered and coded by
`a binary C(57, 40) shortened c y c l i c code. I f t h e
`channel b i t error r a t e i s
`then b i t e r r o r
`r a t e a f t e r decoding f o r the synchronization word
`i s
`which i s a reasonable value.
`frames
`t h e
`To p r o t e c t
`t h e
`i n f o r m a t i o n o f
`against channel errors,
`codes are
`two U.E.P.
`designed. These codes, which are constructed by
`t h e Blokh-Zyablov c o n s t r u c t i o n method have r e s ec-
`t i v e l y (745, 5366, 3372) (code 1 ) and (5354, &2)
`these vectors
`(code 2) separation vectors. As
`show,
`the f i r s t code has three l e v e l s o f protec-
`R o f
`the whole
`t i o n
`( t h e average
`redundancy
`channel encoder ( t h e frame-length and the U.E.P.
`p r o t e c t i o n b i t s ) i s U. X) w h i l e the second code
`has two l e v e l s o f p r o t e c t i o n ( R = 10 X). The B i
`codes used
`t o construct
`these b.E.P.
`codes are
`summarized i n t a b l e 1. The performance o f these
`
`320.5.4.
`
`0901
`
`Apple Inc. Exhibit 1005 Page 4
`
`

`

`codes are presented i n Fig. 7 : the U.E.P.
`U.E.P.
`code with three l e v e l s e x h i b i t s higher performance
`than the code with two l e v e l s o f protection.
`The subjective performances o f
`t h i s U.E.P.
`code w i t h 3 l e v e l s and the binary BCH (127, 113,
`code ( w i t h 11 !%
`5) equal-error-protection
`(E.E.P.)
`o f redundancy) are presented i n f i g . 8. As
`these
`p i c t u r e s i l l u s t r a t e , f o r channel b i t e r r o r r a t e P
`=
`(a very c r i t i c a l value) the U.E.P.
`code i s
`b e t t e r than the BCH EEP code.
`CONCLUSION
`the problem o f designing a
`I n t h i s paper
`combined source-channel encoding has been conside-
`red. The s e n s i t i v i t y f a c t o r o f each b i t (being the
`measure o f importance o f each b i t ) i n the trans-
`m i t t e d frame
`i s measured
`f o r
`two sequences o f
`images. These curves showed c l e a r l y
`t h a t an
`U.E.P.
`code i s desirable,
`t o protect, w i t h d i f f e -
`r e n t
`l e v e l s o f protection,
`the most
`important
`information a t the output o f the variable-length-
`encoder. The performances o f two U.E.P.
`codes have
`been investigated. The code of
`three l e v e l s o f
`p r o t e c t i o n w i t h 11 % o f average redundancy
`i s
`considered as the best candidate f o r t h i s applica-
`t i o n .
`REFERENCES
`5. Guichard and D. hasse "L'image Numdrique e t
`1:
`l e Codage".
`L'Echo des Recherches n o 126,
`21-36. 1986
`hodestino, D.L. Daut and A.L.
`5.W.
`Vickers
`"Combined source-channel coding o f images using
`the block cosines Transform" I.E.E.E.
`Trans. on
`Com. Vo. 29 pp. 1261-1273 Sept. 1981
`I
`D.R. Comstock and J.D. Gibson "Hamming coding
`o f DCT compressed images over noisy channels"
`IEEE Trans. on Com. Vol. 32 pp.856-861, July 84
`W.H. Chen and W.K. P r a t t "Scene adaptive coder"
`IEEL Trans. on Corn. vol. 32, n o 3, March 84.
`T. Ferguson and 3.H. Rabinowitz "Self synchro-
`IEEE Trans. on I T . vol.
`n i z i n g Huffman Codes",
`I
`30, n o 4, July 84.
`2. hagenauer, N. Seshadri and C.E.W.
`SudberG
`"Variable-rate
`sub-band
`speech
`coding and
`natched
`channel
`coding
`f o r mobile
`r a d i o
`I.E.E.E.
`Vehicular
`Technology
`channels"
`Conference, VTC-88, Philadelphia, Pennsylvania,
`h e 88.
`B. Masnick and 3. Wolf
`"On
`I.E.E.E.
`srror-protection codes",
`I
`vol. 13 pp. 600-607 July 1967
`-.A. Dunning and W.E. Robbins "Optimal encoding
`o f l i n e a r block codes f o r unequal e r r o r protec-
`tion".
`I C Vol. 37, pp. 150-177, 1978
`9.
`W.J.
`van G i l s "Linear-unequal-error-protection
`codes from shorter codes".
`I.E.E.E.
`Trans. on
`I T , vol. 30 pp. 544-545, May 1984
`E.L. Blokh, V.V.
`Zyablov "Coding o f generali-
`ed
`cascade
`codes".
`Problemy
`Peredachi
`I n f o r m a t s i i , vol. 10, n o 3, 1974
`V.V.
`"Codes w i t h
`V.A.
`Zinovev,
`Zyablov
`unequal-protection o f
`information symbols".
`Probl. Pered.
`Inform. Vol. 15, n o 3, pp.50-60,
`1979
`
`2.
`
`3.
`
`4.
`
`5.
`
`6.
`
`l i n e a r unequal-
`Trans. on I T ,
`
`7.
`
`8.
`
`10.
`
`11.
`
`I
`I
`I
`I
`
`pig.- Sourcrencoder blacbdiagran
`
`V.L.
`
`1 SW I DC I AC I
`- 10 bits (6-7
`DC : The first DCT coefficient - 9 bits
`- 8 bits
`su : Synchronization word
`V.L. : 4 DCT blocks coded in VLC - Variable-length
`AC : activities of blacks
`m- "he constituents of each frame
`
`frame-length)
`
`h K - Z ai
`C - G k
`
`iil
`
`G * NK matrix
`
`Figure Zb : the Blokh-Zyablor code constructioa
`
`U.E.P.
`
`1
`
`U.E.P. 2
`
`B1 (63, 4 5 ) over GF (2)
`B2 ( 6 3 , 61) over GF (Z6)
`
`B3 (63, 62) over GF (Z6)
`
`B1 (63, 59) over GF (Z6)
`B2 ( 6 3 , 62) over GF (Z6)
`
`TABLE 1 : The mbcodes of II.E.P.-Bi
`
`codes
`
`(UEP-encoder) t j , H z t
`
`(BSC)
`
`Source-encoder (Channel-encoder
`
`- The combined soureechomuel encoding s c b
`
`0902
`
`320.5.5.
`
`Apple Inc. Exhibit 1005 Page 5
`
`

`

`j
`Fig.4 Factor of bit error sensitivity
`
`a ) Coded image. No channel e r r o r s
`SNR = 3 4 , 8 dB
`
`100 800
`
`b ) Coded image + BCH-EEP Code
`SNR = 32,s dB)
`(P =
`
`.
`100
`
`.
`200
`
`.
`300
`
`.
`4 0 0
`i
`Fig.5 Orderd factor or bit error sensitivity
`
`
`500
`
`600
`
`1 E-01
`
`1 E-02
`
`1 E-03
`
`1E-04 -
`
`n 1E-05
`
`1 E-06
`1 €-or
`
`Fig.6 Optimal error rate for each bit
`
`lE-GI
`
`,
`100
`
`100
`
`I
`300
`
`600
`
`~
`
`800
`
`100
`
`~
`800
`
`~
`
`400
`I
`Fig.7 Performaces of U.E.P codes
`
`~
`
`~
`
`(
`
`C ) Coded image + BZ-UEP Co