KR100249046B1 - Device for retrace in trellis decoder - Google Patents

Abstract

The present invention is directed to a grid alliance (Trellis Decoder) for a Grand Alliance (Vesigital Side band) 8VSB using a Viterbi decoding algorithm in a system for receiving digital transmission standards such as HDTV (High Definition TV). The present invention relates to backtracking, and the present invention provides a first activation signal and address capable of reading a survivor path stored value only once every 4 symbol data inputs, and at the same time, delays the read survivor path value. 2 generates an activation signal, and the traceback unit reads the survivor path information stored according to the first activation signal and the address and inputs the survivor path information of the decoded lower bits and its state output value from the survivor path information read. During the transition process, the decoded values of the lower bits are traced back. The data delay unit sequentially delays the decoded data output from the back tracker by a predetermined bit and outputs one byte of decoded data for each back trace.

Description

Backtracking device of grid decoder

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a system for receiving digital transmission standards such as HDTV (High Definition TV). In particular, a Grand Alliance (hereinafter, abbreviated as 'GA') using a Viterbi decoding algorithm is referred to as 8VSB ( The present invention relates to a back trace of a trellis decoder for a vesigital sideband.

In general, digital communication systems use error control and correction techniques to overcome channel disturbances such as noise and fading.

The error correction technique includes a channel encoding technique on the transmitting side and a channel decoding technique on the receiving side. A convolutional encoder is mainly used for the encoding technique, and a Viterbi decoder is used for the decoding technique.

As shown in FIG. 1, the convolutional encoder of the encoding technique includes a 2-bit shift register 11 and two adders 12 and 12 'that perform modulo-2 addition. The outputs G1 and G2 are determined by the state of the shift register 11 and the input 13, and the output state according to time is shown in the trellis diagram of FIG. 2.

Each point in the lattice diagram of FIG. 2 represents a state that the shift register 11 may have, a branch of a solid line indicates a transition when the input is' 0 ', and an input having a dotted line is' The transition when 1 'is shown, and the number displayed on each branch indicates the values of G1 and G2 output when the branch transition occurs. At this time, as two paths are combined in each state, the Viterbi decoder at the receiving side selects only the probable paths among the two paths by a Viterbi decoding algorithm called Maximum Likelihood Decoding. And the path that is not possible is discarded. The selected path is called a survivor path, and a survivor path (decision depth or truncation depth) determined by each state (for example, a thick solid line of FIG. 2 is represented by state 1 (01). Information about the survivor's path).

Therefore, the decoding by the Viterbi algorithm is performed by selecting and tracebacking the most likely survivor path among the survivor paths maintained by each state.

As shown in FIG. 3, the lattice decoder based on the Viterbi algorithm is a branch metric for calculating a branch metric between the received input code 21 and the reference value of each branch of the lattice diagram. Mertic) arithmetic unit 22, an ACS (Add-Compare-Select) arithmetic unit 23 that selects survivor paths in each state and calculates a state metric of the survivor paths; Normalization arithmetic unit 24 for subtracting similarity values, State Metric Memory 25 for storing state values, and Maximum likelihood value detection for detecting the most probable survivor paths among survivor paths in each state Inverse values are respectively output from the device (Maximum Likelihood Value Detection) 26, a path memory 27 storing information on survivor paths of each state, and the maximum likelihood value detection device 26. Trace back to run the trace unit) 28.

As shown in FIG. 4, the backtracking device 28 is composed of a path storage device 31, a multiplexer 32, and a register 33, which is a storage device for storing survivor paths as much as the depth of determination. The size of the register 33 corresponds to K (resistance length) -1, and the size of the path storage device 31 is M (= 2 ^K-1 ) * L (decision depth), and the multiplexer 32 is M: 1 multiplexer is required.

The backtracking by the backtracking device of the grid decoder having such a configuration is performed by using survivor path information in each pre-stored time unit.

That is, the state at the time unit j m _j = a survivor information of _j b _j s _mj one time, the state of the former from the state of the time unit j-1 present on the survivor path m _j-1 = a _j-1 b _j-1 is m _j-1 = b _j s _mj . At this time, since the structure of the convolutional encoder can know that b _j = a _j-1, s _mj = b _j-1 , the decoding detects a state having a minimum value in every unit of time and stores a path from the state having the minimum state value. The survivor route information stored in the device is used to determine the whole state, and this process is repeated as much as the Decision Depth (hereinafter, abbreviated as 'L').

5 is a structure of a trellis code interleaver used in the ATSC 8VSB mode, and Table 1 below shows the output of the trellis code interleaver.

<Table 1>

segment Block 0 Block 1 ... Block 68 012 D0 D1 D2 ... D11 D4 D5 D6 ... D3 D8 D9 D10 ... D7 D0 D1 D2 ... D11 D4 D5 D6 ... D3 D8 D9 D10 ... D7 ......... D0 D1 D2 ... D11 D4 D5 D6 ... D3 D8 D9 D10 ... D7

The grid code interleaver of FIG. 5 includes an input terminal 41 for receiving interleaver data, an output terminal 43 for arranging and outputting lattice-coded data and pre-coded data accordingly, and the input terminal 41 and the output terminal 43. And a lattice encoder 42 comprising 12 lattice encoders and a precoder having the same structure.

In the above description, the twelve lattice encoders and the precoder denote the first to twelfth lattice encoders and the precoder, respectively, in the order of 42a to 42l from the top to the bottom.

In the lattice code interleaver configured as described above, data in byte units output from a convolutional interleaver is processed in units of bytes by each of the 12 convolutional encoders. Each byte unit data generates four symbols of encoded data through one encoder. The symbol data input to the convolutional encoder is input by 2 bits from the most significant bit (MSB). Since the data of each byte unit is encoded through one convolutional encoder, twelve times of byte unit data are required to be encoded through the twelve convolutional encoders.

One segment is composed of 828 symbols, that is, 207 bytes of data, which is not a multiple of 12. Therefore, four segments (828 = 12 * 69 bytes) are converted to convert byte data into symbol data. The first symbol (7,6) of the first byte data in the field is encoded by the first lattice encoder and the precoder (42a), and the first symbol (7,6) of the second byte is the second lattice encoder. And coded via the precoder 42b, and the first symbols 7 and 6 of the 12th byte are coded through the twelfth lattice encoder and the precoder 42l. The second symbol (5,4) of the first byte in the segment is encoded by the first lattice encoder and the precoder 42a, and the second symbol (5,4) of the second byte is the first lattice encoder and the precoder ( Each byte data is encoded in symbol units in a manner inputted to 42b).

The four encoders corresponding to the sync signal section in the segment sync signal section do not output the encoded symbol data because no symbol data is input. The four symbol data are inputted to each encoder after being delayed for 12 cycles and encoded. Therefore, as shown in Table 1, in the first segment of each field, symbol data encoded in a normal order from the first lattice encoder and the precoder 42a to the twelfth lattice encoder and the precoder 42l is output. However, in the second segment, symbol data from the fourth trellis encoder and the precoder 42d to the twelfth trellis encoder and the precoder 42l are first outputted, and then the third trellis encoder and the precoder 42a to the third segment. Coded symbol data up to the trellis encoder and precoder 42c are output. In the third segment, from the ninth lattice encoder and the precoder 42i to the twelfth lattice encoder and the precoder 42l, and then from the first lattice encoder and the precoder 42a to the eighth lattice encoder and the precoder 42h. Coded symbol data up to is output. This three-segment pattern is repeated in the field so that the data symbols after the data segment synchronizing signal is inserted have a distance of 12 symbols.

6 is a grid code deinterleaver, comprising: a data input terminal 51 for receiving quantized and phase corrected coded data, a data output terminal 53 for outputting grid decoded data, and a data input terminal 51; The grating decoder 52 is provided between the data output terminals 53 and has the same structure.

In the above, the twelve lattice decoders 52 denote the first to twelfth lattice decoders, respectively, by the symbols 52a to 52l in order from top to bottom.

Here, each lattice decoder has the same structure as in Fig. 3, and its functions and actions are also the same.

In addition, each lattice decoder operates as a symbol clock, and outputs one byte of decoded data every four symbol clocks after receiving symbol data of a decision depth L.

The operation of the lattice code deinterleaver having the above configuration is as follows.

The symbol data of the first segment in the received field is input to the first lattice decoder 52a, the second symbol data to the second lattice decoder 52b, and the twelfth symbol data to the twelfth lattice decoder 52l. It is input and decoded.

That is, it is divided into 12 groups of (1, 13, 25, ...), (2, 14, 26, ...), ..., (12, 24, 36, ...). Since no data is input to the four lattice decoders corresponding to the input order in the segment synchronization signal section, invalid data is output as the output of the lattice decoder. Here, the symbol data of 12 clocks is input to the four lattice decoders corresponding to the segment synchronization signal section, and are decoded.

Accordingly, the last symbol data of segment 0 is inputted to the twelfth lattice decoder and decoded, but the first symbol data of segment 1 is input to the fifth lattice decoder and not decoded. That is, the decoding order of the grid decoder in segment 1 is (# 4, # 5, ..., # 11, # 0, ..., # 3). This is because a 4-symbol clock amount of segment synchronization signal is inserted between the last symbol data of segment 0 and the first symbol data of segment 1. In the same concept, in segment 2, in the order of grid decoder (# 8, # 9, ..., # 0, ..., # 7), in segment 3, again (# 0, # 1, .. Decode in the order of.

On the other hand, since the transmitter of the GA 8VSB mode performs 12 symbol intra-segment interleaving, the receiver requires 12 identical lattice decoders. Since the twelve lattice decoders have only one symbol for every twelve symbols in the symbol sequence input to the receiver, the branch matrix arithmetic unit, the ACS arithmetic unit, the maximum likelihood detector, and the normalization arithmetic unit are time-divided in the twelve lattice decoders To share.

7 is a timing diagram of symbol clock a, input data b, and symbol data c-e input to each lattice decoder.

As shown in FIG. 7, it can be seen that each lattice decoder has a time margin of 11 symbols between input symbol data. Therefore, each lattice decoder can complete backtracking before new symbol data is input. If the symbol clock fs is used as it is, the backtrace of the decision depth L = 11 can be performed. If 2fs is used, the backtrace of the decision depth L = 22 can be performed. To maintain a segment error rate of 3 * 10 ^-6 or less at SNR = 14.9dB of the ATSC DTV standard, the decision depth L = 22 is reasonable.

Each lattice decoder decodes one symbol (2-bit data) by performing backtrace on every symbol input. Since a convolutional deintereaver connected to the output of the grid decoder processes input data in bytes, each grid decoder must generate 1 byte of decoded data through four back traces.

However, performing backtrace for every symbol input to obtain 1 byte of decoded data means that 4 backtraces must be executed, and the survivor path storage device of FIG. 4 must be accessed 88 times. This, in turn, increases the frequency of transitions, increasing power consumption in CMOS ASIC circuits. Increasing power consumption in CMOS ASIC circuits generates heat, which requires special packaging to increase the cost of ASIC fabrication.

Accordingly, the present invention has been proposed to solve the above problems of the conventional backtracking device, and its purpose is to perform a backtracking every 4 symbol inputs without performing backtracking for every symbol input in a GA 8VSB grid decoder. In addition, the present invention provides a backtracking device of a grid decoder that generates one byte of decoded data in one backtracking.

Apparatus according to the present invention for achieving the above object,

Control means for generating a first activation signal and an address capable of reading the survivor path stored value only once every four symbol data inputs, and simultaneously generating a second activation signal capable of delaying the read survivor path value;

Read the survivor path information stored according to the first activation signal and the address generated by the control means, and perform the state transition process by inputting the survivor path information of the decoded lower bit and its state output value among the read survivor path information. Backtracking means for backtracking the decoded value of the lower bit;

And a data delay means for delaying the decoded data outputted from the traceback means by a predetermined bit and delaying the decoded data of 1 byte for each traceback.

1 is a block diagram of a general weaving encoder;

2 is a lattice diagram according to the weaving encoder of FIG.

3 is a block diagram of a Viterbi decoder using a general Viterbi decoder;

4 is a block diagram of an example backtracking device using a RAM;

5 is a block diagram of a conventional grid code interleaver;

6 is a block diagram of a conventional grid code deinterleaver;

7 is a symbol clock and data timing diagram of a conventional lattice decoder;

8 is a block diagram of the traceback device of the lattice decoder according to the present invention;

9 is a detailed configuration diagram of the traceback part of FIG. 8;

10 is a timing diagram between symbol data and an active signal in the present invention.

<Description of the code | symbol about the principal part of drawing>

60: control unit 70: backtracking unit

71: storage unit 72: multiplexing unit

72a, 72b: first and second multiplexer 73: backtracker

73a: 3-bit register 80: data delay

81-84: first to fourth delayers

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings.

8 is a block diagram of a backtracking device of a lattice decoder according to the present invention.

As shown in the figure, a first activation signal and an address capable of reading the survivor path stored value are generated only once every 4 symbol data inputs, and at the same time, a second activation signal capable of delaying the read survivor path value is generated. A controller 60; Read the survivor path information stored according to the first activation signal and the address generated by the controller 60, and the state transition process by inputting the survivor path information of the decoded lower bits and its state output value among the read survivor path information. A backtracking unit 70 for backtracking the decoded value of the lower bit while performing; And a data delay unit 80 that delays the decoded data output from the back tracker 70 by a predetermined bit and delays and outputs the decoded data of 1 byte for each back trace.

In the above, the backtracking unit 70, as shown in Fig. 9, stores a survivor path information as much as the decision depth, and the 16-bit survivor path information outputted from the storage device 71. A multiplexer 72 consisting of two 8: 1 multiplexers 72a and 72b for decoding a second signal, survivor path information of the decoded lower bits of the output of the multiplexer 72, and its state output value It is composed of a back tracker (73) to back track the decoded value of the lower bit while performing the state transition process.

In the above, the memory device 71 is composed of 16 * L single port RAM, and the multiplexer 72 multiplexes only the upper 8 bits of the 16-bit survivor information output from the memory device 71. A first multiplexer 72a and a second multiplexer 72b for multiplexing only the lower 8 bits of the 16-bit survivor information output from the storage device 71 are provided.

In addition, the back tracker 73 receives the survivor path information of the decoded lower bits output from the second multiplexer 72b in the multiplexer 72 and its state output value and performs a state transition process. It consists of a 3-bit register 73a that traces back the decoded value of the bit.

In addition, the data delay unit 80 sequentially delays two bits of decoded data generated through the back trace in the back trace unit 70, and outputs one byte of decoded data during one back trace. The fourth retarders 81 to 84 are configured in series connection.

The backtracking process of the backtracking apparatus according to the present invention configured as described above is performed inversely for every 4 symbol inputs using a modulo-L down counter (not shown in the figure) in the controller 60. By generating the first and second activation signals (activation signal_1, activation signal_2) such as (b) and (c) of FIG. 10 to enable tracking, the traceback unit 70 and the data delay unit ( Start by activating 80).

Here, the first activation signal (activation signal_1) shown in FIG. 10 (b) is activated once every four symbol inputs, and the survivor path value stored in the memory device 71 is read only during the activation period. This signal causes the trace to run.

In addition, the second activation signal (activation signal _2) shown in FIG. 10C is similarly activated once every four symbol inputs, and the activation period is during the last four clock periods of backtracking, and this activation period During this time, only two bits of decoded data are stored in the delay units 81 to 84, thereby outputting one byte of decoded data to every four symbol data inputs, and maintaining the value until the next traceback.

The controller 60 generates a read address of the memory device 71 in addition to the first activation signal (activation signal_1) and transmits the read address to the traceback unit 70.

The back tracker 70 outputs survivor information stored in the L-1 address stored in the memory device 71 by the first activation signal (activation signal_1) and the read address. In this case, the back tracker 73 The back tracker 73 starts back tracking using the state value stored in the 3-bit register 73a and the survivor information stored in the L-1 address of the storage device 71.

The survivor path information stored in the storage device 71 is 2 bits for each state. The upper bits of the stored 2-bit information are survivor information associated with the upper bits during encoding, and the lower bits are survivors associated with the lower bits during encoding. Information.

The 16-bit survivor information output from the storage device 71 is input to each of the two multiplexers 72a and 72b in the multiplexer 72 in 8-bit units. In particular, the upper 8 bits of the survivor information of each state are included. Only the upper bits are input to the first multiplexer 72a, and the lower 8 bits are composed of only the lower bits of survivor information of each state and input to the second multiplexer 72b.

Since the upper 8 bits are not encoded at the encoder side of the transmitter, the output of the first multiplexer 72a is decoded data as it is, and the lower 8 bits are decoded through a backtracking process as they are encoded and transmitted.

In this case, the first and second multiplexers 72a and 72b are determined by the output of the 3-bit register 73a, and the input of the 3-bit register 73a is the output of the 3-bit register and the second multiplex. It is determined by the output of the firearm 72b.

The second multiplexer 72b and the 3-bit register 73a are state machines, and state transitions occur every clock. This state transition process is a backtracking process.

In addition, the value of the final state determines the decoding output of the lower bit, and when the 3-bit register 73a reaches the final state through the backtracking process, the first multiplexer 72a outputted by the state value is output. The output of is the decoded value of the upper bit and the decoded value of the lower bit is determined by the combination of the final state values.

That is, the 19th, 20th, 21st and 22nd values determine the decoded output of the lower bits. When the three-bit register 73a reaches the nineteenth state through the backtracking process, the output of the first multiplexer 72a outputted by the state value becomes the decoded value of the upper bit and the decoded lower bit. The value is determined by the combination of the nineteenth state values. The two-bit data generated in this way becomes the lowest symbol of the one-byte data. In the same way, the next symbol data is determined by the 20th and 21st states, and the highest symbol data is determined by the 22nd state, and the first trace is performed. Decoded data of 1 byte is determined and outputted through.

Here, the first to fourth delayers 81 to 84 in the data delay unit 80 sequentially delay the 2-bit decoded data generated through the back trace in the back trace unit 70, and perform one back trace. This function outputs decoded data of 1 byte per hour (one delay unit stores 2 bits, thus 2 bits * 4 delays = 8 bits).

As described above, the present invention does not perform backtracking for every symbol input, but performs backtracking for every four symbol inputs, and can generate decoded data of one byte in one backtracking. Reduction (switching the frequency of transitions) has the advantage of reducing the power consumption of CMOS ASIC circuits.

In addition, the above-described advantages can eliminate the special packaging (heat removal circuit) added separately to suppress the heat generated as in the conventional, there is an advantage that can reduce the manufacturing cost when manufacturing the ASIC of the grid decoder.

Claims (8)

In the backtracking device of the grid decoder for obtaining the decoded data through backtracking, Control means for generating a first activation signal and an address capable of reading the survivor path stored value only once every four symbol data inputs, and simultaneously generating a second activation signal capable of delaying the read survivor path value; Read the survivor path information stored according to the first activation signal and the address generated by the control means, and perform the state transition process by inputting the survivor path information of the decoded lower bit and its state output value among the read survivor path information. Backtracking means for backtracking the decoded value of the lower bit; And a data delay means for sequentially delaying the decoded data output from the backtracking unit by a predetermined bit and outputting one byte of decoded data for each backtracking. The method of claim 1, The control means uses a 21.5 MHz clock twice as fast as a symbol clock of 10.7 MHz when generating an address for reading survivor path information in the backtracking means, before the next depth data is inputted. A trace decoder of a grid decoder, characterized in that a read address is generated to enable traceback up to 23. The method of claim 1, The backtracking means is a backtracking apparatus of a grid decoder, characterized in that the backtracking is performed once for four symbol inputs. The method of claim 1, The backtracking means comprises: a multiplexer comprising a storage device for storing survivor path information at a determined depth, a predetermined 8: 1 multiplexer for decoding 16-bit survivor path information output from the storage device, and an output of the multiplexer. And a back tracker that traces the decoded value of the lower bit while performing a state transition process by inputting survivor path information of the decoded lower bit and its state output value. The method of claim 4, wherein And the memory device is composed of a single port RAM of 16 * L (depth of crystal). The method of claim 4, wherein The multiplexer is a first multiplexer that multiplexes only the upper 8 bits of the 16-bit survivor information output from the storage device, and a second multiplexer which multiplexes only the lower 8 bits of the 16-bit survivor information output from the storage device. Back tracking device of the grid decoder, characterized in that configured. The decoding apparatus of claim 4, wherein the back tracker receives the decoded values of the lower bits while performing a state transition process by inputting the survivor path information of the decoded lower bits output from the second multiplexer in the multiplexer and its state output value. Backtracking device of a grid decoder, characterized by consisting of a three-bit register to trace back. The method of claim 1, The data delay means sequentially delays the 2-bit decoded data generated by the backtracking from the backtracking means, and the first to fourth delayers for outputting the decoded data of 1 byte during one backtracking are connected in series. Back tracking device of the grid decoder, characterized in that configured.