State Diagram:Since the encoder is a linear sequential circuit,its behavior can be described by a state diagram.The encoder state at time is represented by the message ◆ The encoder of the (2,1.2)convolutional code given in the example has 4 possible states,and its state diagram is shown in the figure below. 000 00 011 output 0 0/01 0/10 11 1/01 label=input/output Trellis diagram:The state diag gram can be expanded in time to display the state transition of a convolutional encoder in time.This expansion in time results in a trellis diagram. state 110 010 100 001 010y 0 The encoding of a message sequence u is equivalent to tracing a path through the trellis. The trellis structure is very useful in decoding a convolutional code. 6
6 State Diagram: Since the encoder is a linear sequential circuit, its behavior can be described by a state diagram. The encoder state at time l is represented by the message bits stored in the memory units. The encoder of the (2, 1, 2) convolutional code given in the example has 4 possible states, and its state diagram is shown in the figure below . 00 01 10 11 0/00 1/11 1/00 0/01 1/01 0/10 1/10 0/11 input output label = input/output Trellis diagram: The state diagram can be expanded in time to display the state transition of a convolutional encoder in time. This expansion in time results in a trellis diagram. The encoding of a message sequence u is equivalent to tracing a path through the trellis. The trellis structure is very useful in decoding a convolutional code
IV.Conventional Coding 1.Types of codes [block codes-linear codes,cyclic codes convolutional codes classfication based on structure [random-error-correcting codes burst-error-correcting codes (Binary codes Nonbinary codes error-correction codes error-detection codes 2.Error correcting capacity The error correcting capacity of a code Cdepends on its distance structure. The Hamming distance between two codewords,x and y,in a code,denoted by d(x,y),is defined as the number of places in which they differ. 4L)=立4Gdk,)=fx≠y 10,ifx,=y. ord(y){i:x≠yl For example,dy(010,111)=2. d(30102,21103)=3 Hamming distance satisfies the axioms for a distance metric: I)dm(x,y)≥0，with equality iffx=y 2)dn(,y)=dn(y,x)(对称性) 3)du(x.y)sdu(x,z)+du(z.y) The minimum Hamming distance of a code C is defined as dmin{dn(k,y)lx,y∈C,x≠y} For a convolutional code.this minimum Hamming distance is usually called the minimum free distance,denoted byd An(n,k)block code with minimum Hamming distance d is capable of correcting
7 IV. Conventional Coding 1. Types of codes block codes - linear codes, cyclic codes classfication based on structure convolutional codes ⎧ ⎫ ⎨ ⎬ ⎩ ⎭ random-error-correcting codes burst-error-correcting codes ⎧ ⎨ ⎩ Binary codes Nonbinary codes ⎧ ⎨ ⎩ error-correction codes error-detection codes ⎧ ⎨ ⎩ 2. Error correcting capacity The error correcting capacity of a code C depends on its distance structure. The Hamming distance between two codewords, x and y, in a code, denoted by H d (, ) x y , is defined as the number of places in which they differ. H H 1 H 1, if ( , ) ( , ), ( , ) 0, if or ( , ) |{ : }| n i i Hii ii i i i i i x y d d xy d xy x y d ix y = ⎧ ≠ = = ⎨ ⎩ = = ≠ x y ∑ x y For example, (010,111) 2, (30102,21103) 3 H H d d = = Hamming distance satisfies the axioms for a distance metric: 1) ( , ) 0, with equality iff H d x y ≥ = x y 2) ( , ) ( , ) ( ) H H d d xy yx = 对称性 3) ( , ) ( , ) ( , ) H HH d dd x y ≤ + xz z y The minimum Hamming distance of a code C is defined as d d min min ( , ) | , , { H xy xy x y ∈C ≠ } For a convolutional code, this minimum Hamming distance is usually called the minimum free distance, denoted by free d . An (n, k) block code with minimum Hamming distance min d is capable of correcting