CN100477534C

CN100477534C - decoding circuit and method for viterbi decoder

Info

Publication number: CN100477534C
Application number: CNB021305323A
Authority: CN
Inventors: 郭弘政; 吴文义
Original assignee: MediaTek Inc
Current assignee: MediaTek Inc
Priority date: 2002-08-14
Filing date: 2002-08-14
Publication date: 2009-04-08
Anticipated expiration: 2022-08-14
Also published as: CN1476176A

Abstract

A decoding circuit of a Viterbi decoder comprises a branch measurement unit, an addition-comparison-selection unit and a path memory unit, wherein the path memory unit comprises a data flow controller, a traceback write register array, a waiting register array and a decoding register array. The run-length limited code is used to solve the complex trellis diagram of Viterbi decoder after longitudinal arrangement, and the register array can have other actions at different time, so that it has no need of large number of registers to process data, and can attain the goal of decoding high-speed Viterbi decoder.

Description

The decoding circuit of Viterbi decoder and method

Technical field

The PRML that the present invention relates at CD (Partial Response Maximum Likelihood, PRML) decoding circuit and the method for a kind of Viterbi (Viterbi) decoder in the system, specifically, the decoding circuit and the method that relate to a kind of like this Viterbi decoder in the PRML of CD system, this circuit and method are utilized RLL sign indicating number (Run Length Limited Code, RLL code) effectively solves trellis structure complicated trellis structure after vertically putting in order of Viterbi decoder, and do not need a lot of register of quantity to come deal with data.

Background technology

In the PRML system of CD such as DVD (digital versatile disc, digital versatile dish), can its characteristic be described with trellis structure (trellisdiagram) for a transmission channel (transmission channel) with internal memory.For example the input signal EFMP of DVD channel is a binary signal, and channel memory length (channel memory length) is 2, so 4 states (state) are arranged on the trellis structure, and each state has two branches (branch).8 branches in each state, have been comprised, represent the signal that this transmission channel spreads out of in each unit interval, can be one of them in these eight the possibility signals, value as for these eight kinds of signals, shown in the channel model schematic diagram of Figure 1A, channel model (channel model) can obtain following expression formula substitution 1/-1 as can be known thus:

(" current input "+k ₁* " in the previous input of first internal memory "+k ₂* " in the previous input of second internal memory ")

In Figure 1A, k ₁With k ₂Reflect the characteristic of this channel in the enforcement, k ₁With k ₂Value can be given in advance, use integer filter (shaping filter) to make the characteristic tends of overall channel be bordering on this value then.This integer filter can be partial response equalizer (Partial response equalizer).Another kind method is not go to change the characteristic of channel, but directly estimates k ₁With k ₂Value, i.e. signal level estimation (signal levelestimation).No matter take which kind of mode, the respective value in each branch in the trellis structure shown in Figure 1B in a word will be because of k ₁With k ₂Determine after and can determine.

Figure 2 shows that the block diagram of Viterbi decoder.In Fig. 2, Viterbi decoder 200 comprises branch metric (Branch Metric) unit 202, ACS (Add-Compare-Select adds-compare-select) unit 204 and path internal storage location (Path Memory Unit, PMU) 206.The reference level that digital signal that branch metric unit 202 reception prime transducers (not illustrating) are exported and reference level generation unit (not illustrating) are exported calculates a branch metric thus, and exports this branch metric to ACS 204.ACS 204 carries out computings such as addition, comparison and selection according to this branch metric, thereby obtains a path metric (path metric), and exports this path metric to path internal storage location 206.Path internal storage location 206 receives the path metric that ACS 204 are exported, work such as restraining thus, merge and decode, and obtaining decoded signal, and the demodulator (not illustrating) that this decoded signal is exported to afterwards grade.To do more detailed description to Viterbi decoder 200 below.

Fig. 3 illustrates the decode procedure of Viterbi decoder.In Fig. 3, if receive three continuous received signals (received signals) R1, R2, R3, find corresponding with it most possible signal, at first at each the bar branch in the trellis structure, Viterbi decoder can be calculated branch metric (the branch metric unit 202 by Fig. 2 is carried out).Calculation mode is generally the square value of signal difference or the absolute value of signal difference, for example BM _00-00=[R1-(1.8)] ²Or | R1-(1.8) |.Add up and the path metric of so-called a certain paths is exactly all pairing branch metrics of branch that this path is contained, for example the thick black line among Fig. 3 is by State _{00 at 1T}(literal among the symbol in this subscript " at " and Fig. 3 " " corresponding, hereinafter also be like this) through State _{00 at 2T}Pass through State again _{00 at 3T}Arrive State at last _{00 at 4T}This paths, and path metric is exactly " BM _00-00+ BM _00-01+ BM _01-11".

Certainly, the path can be so not short in the ordinary course of things, as above-mentioned path at State _{00 at 1T}Should just pass by stretch directly, so in fact the correct path metric of this paths should be that " this path is accumulated to State before _{00 at 1T}The time path metric "+" BM _00-00+ BM _00-01+ BM _01-11".Observe trellis structure more as can be known, each path constantly intersects on each state in fact, and the variation of free routing after intersecting all is identical in fact, so Viterbi is found to guarantee still can calculate optimal path at last as long as select optimal path herein to continue to extend at each state.But computational complexity but can therefore and significantly reduce.The action of this " each state selects optimal path herein to continue to extend " is called survival Path selection (survivor path selection), and the path of surviving exactly, the path of electing.

In Fig. 3, be described in State _{00 at 2T}The survival path be how by from State _{00 at 1T}The survival path with from State _{00 at 1T}The survival path pick out, with reference to figure 3, at State _{00 at 2T}Survivormetric SM _{00 at 2T}Be that column operations obtains under the basis:

SM _00?at?2T＝min{[SM _00?at?1T+BM _00-00]；[SM _10?at?1T+BM _10-00]}

This expression formula is exactly the ACS unit.Since the ACS element memory feedback loop (feedbackloop) (by each state of survivor metric all can rerun once more cause), make that Viterbi decoder at a high speed is difficult for realizing, and therefore ACS becomes the bottleneck of speed.

According to the deduction of Viterbi decoder, after the action of each ACS, must obtain optimal path, so as long as continuous record is respectively survived the path, after lump-sum data decode by the time finished, the record that migrates out best survival path again was just passable.But two shortcomings are so arranged, and at first are that decoding hides Paths can be oversize, and secondly, if Path too long, then being used for the hardware quantity of memory can very big (this hardware be called the path internal storage location).

Shown in the convergence schematic diagram of the deduction decoding of in trellis structure, using Viterbi decoder as shown in Figure 4, Viterbi is deduced, and individual characteristic is arranged is exactly after trellis extended the length of 4～6 times of channel memories (channelmemory), and it is that path with the front can merge (merge) together that there is 99% chance in each path of surviving.Therefore the internal storage location data that only need preserve nearest 4～6 times of channel memories (channelmemory) in path get final product for picking up choosing, and past data can be just discardable after progressively decoding.Therefore, only need Limited resources just can finish the work of path internal storage location, and common method have the exchange of mixing (Shuffle-Exchange) and recall (Trace-Back) two kinds.

Figure 5 shows that the block diagram of trellis structure and mixing and exchanging method.In Fig. 5, the operating principle of mixing exchange is intuition very, be exactly to be equipped with a cover internal memory (normally register array (register array)) for each state on the trellis structure, as state " 00 " corresponding to register array 502, state " 01 " is corresponding to register array 504, state " 10 " is corresponding to register array 506, and state " 11 " is corresponding to register array 508, and these register arrays are used for writing down the survival path of this state.

That is to say, along with advancing of time, the judgement position (as shown in Figure 5-1.8 ,-0.8,0.2,1.2 ,-1.2 ,-0.2,0.8,1.8 etc. numerical value) that new judgement can be constantly mixed by the survival path that each state write down of previous moment in the survival path that each state write down on arbitrary particular moment alternates.As shown in Figure 5, after the length about the signal received quantity is through 4～6 times of channel memory, suppose that just this all path is all to converge to same point, so the numerical value that convergence can be obtained is sent as the signal that decoding is become.Therefore, in fact the length of each register array need only 4～6 times about channel memory.

As shown in Figure 6 shown in trellis structure and the retrogressive method block diagram, the operating principle of recalling is the judgement position (decision bit) on each state of each state (each time point) to be existed in " internal memory of rule " (for example RAM), be each state the depositing it and judge that (for example state " 00 " leaves RAM the 1st row in the position of rule separately, state " 01 " leaves RAM the 2nd row in, below by that analogy), there is not interaction between each state, after the length through 4～6 times of channel memory, as shown in Figure 4, there is merging point (being root) to occur.So can be risen by free position, retrodict and calculate preceding state in the utilization judgement position of leaving, and one the road recalls and can find the merging point in regular turn then.

Yet in implementing utilization, can not separate one each time and merge point and all employ recalling so once, but utilize the method for batch job, data placement be become the configuration of " separate merge after the point, a tunnel solve data then ".Its available four actions are described: V (writing (write-in)), T (reviewing (trace)), I (waiting for (idle)), D (decoding decode)).

Shown in the time-space relationship figure of four of retrogressive method elemental motions, at first with vertical direction, internal memory M1 is when T1 as shown in Figure 7, and the judgement position with each state writes (V) regularly.Then, begin to date back to the merging point by certain state, find the merging point just to give internal memory M4 (on trellis, write down adjacent block, just separate out (D) next time at block M4 then) merging the later judgement position of point at T2.When T3, the data of internal memory M1 are temporarily waited for (I), because it is also not of a specified duration to write (V) time from last time, therefore will wait trellis that the situation that merges takes place, and then in the T4 time, the data in the internal memory M1 merge finally at last.At this moment, the merging that produced of internal memory M2 is put to internal memory M1 to begin decode (D).

With horizontal direction, at certain time point, each memory block carries out V, D, four actions of I, T respectively again.The advantage of retrogressive method is the action of its rule, and each situation of same one-level (stage) is to deposit separately separately, so the degree of difficulty of layout (1ayout) reduces.Shortcoming is to realize with RAM usually, so it is all right to be used in DVD Player, then dislikes too slow but be used in DVD ROM, if gather way with register, then, pay quite high hardware costs, and be not suitable for more expensive internal memory because of retrogressive method is to be divided into four blocks deal with data simultaneously.

Summary of the invention

Therefore the invention provides a kind of Veterbi decoding circuit and method, can solve Viterbi trellis structure complicated trellis structure after vertically putting in order, and not need a lot of register of quantity to come deal with data can reach the purpose of high speed Veterbi decoding equally.

The invention provides a kind of coding/decoding method of Viterbi decoder, this Viterbi decoder has the branch metric unit, adds-compare-selected cell and path internal storage location, the step of the method comprises: at first, the trellis structure that cooperates Viterbi decoder is vertically put in order, vertically put in order trellis structure to obtain one.Then, this vertically puts trellis structure in order according to the RLL code computing, to obtain a run-length restriction trellis structure.Secondly, make the branch metric unit calculate a current input branched measurement value according to this run-length restriction trellis structure.Moreover, by add-compare-selected cell calculates this current input branched measurement value, a next time input branched measurement value and a current state value, to obtain next state value.And, add-compare-selected cell institute result calculated with path internal storage location record, to become a survival path, decoded in the survival path that record is finished.

The invention provides the coding/decoding method of another kind of Viterbi decoder, this Viterbi decoder has the branch metric unit, adds-compare-selected cell and path internal storage location, this path internal storage location comprises the codec register array, review and write register array, waiting register array and add-compare-selected cell, the step of the method comprises: at first, set up the trellis structure that cooperates Viterbi decoder.Then, the trellis structure that cooperates this Viterbi decoder is vertically put in order, vertically put in order trellis structure to obtain one.Then, this vertically puts trellis structure in order according to a RLL code computing, to obtain a run-length restriction trellis structure.Secondly, make the branch metric unit calculate a branched measurement value according to this run-length restriction trellis structure.Moreover, by add-compare-selected cell calculates a current input branched measurement value, a next time input branched measurement value and a current state value, to obtain next state value.Then, by add-compare-selected cell only sets a current output according to this next state value and judges that position and next time output judges the position.Moreover, according to this current output judge the position therewith one on the output next time state value of judging position record last time and the current state value judge.Secondly, judge current state value and the relation of judging the position, will judge that the position writes suitable state value.Then, by add-compare-selected cell sends and judges that the position writes register array to reviewing, and review and obtain a merging value.Then, the judgement position that is stored in the codec register array is during to predetermined quantity, and the codec register array becomes the waiting register array.And, according to the original stored judgement position of waiting register array of merging value decoding.

The present invention proposes a kind of decoding circuit of Viterbi decoder, this decoding circuit has the branch metric unit, adds-compare-selected cell and path internal storage location, the branch metric unit is in order to calculating a branched measurement value, and exports this branched measurement value to adding-compare-selected cell.Add-compare-selected cell is according to the optimal path of this branched measurement value with computing one state value, and export one and judge the position.The path internal storage location comprises: data stream controller adds-compares-judgement position that selected cell is exported in order to reception, and the decision output stream of judging the position to.Review for one and write the judgement position that register array receiving data stream controller is exported, and review and obtain a merging value.Waiting register array writes register array and reviews the merging value that obtains to decode reviewing.And a codec register array is decoded the judgement position that is stored in the codec register array according to reviewing the merging value that obtains.

Therefore the invention provides a kind of decoding circuit and method of Viterbi decoder, utilize RLL code effectively to solve trellis structure complicated trellis structure after vertically putting in order of Viterbi decoder, make ACS can parallelly carry out addition and comparison operation, and register array can have other action concurrently in the different time, so, ACS and PMU do not need a lot of register of quantity to come deal with data, similarly can reach the purpose of the decoding of high-speed vital ratio decoder.

Description of drawings

For above-mentioned purpose of the present invention, feature and advantage can be become apparent, preferred embodiment cited below particularly, and cooperate appended graphicly, be described in detail below:

Graphic simple declaration:

Figure 1A is depicted as the channel model schematic diagram;

Figure 1B is depicted as trellis structure;

Figure 2 shows that the block diagram of Viterbi decoder;

The decoding that Figure 3 shows that Viterbi decoder is deduced;

Figure 4 shows that the convergence schematic diagram of the deduction decoding of in trellis structure, using Viterbi decoder;

Figure 5 shows that the block diagram of trellis structure and mixing and exchanging method;

Figure 6 shows that trellis structure and retrogressive method block diagram;

Figure 7 shows that the time-space relationship figure of four elemental motions of retrogressive method;

Figure 8 shows that the flow chart of the method for Viterbi decoder of the present invention;

Fig. 9 A is depicted as original trellis structure;

Fig. 9 B is depicted as original trellis structure is done horizontal arrangement;

Fig. 9 C is depicted as original trellis structure is done vertical arrangement;

The channel memory that Figure 10 shows that the binary system input is 3 trellis structure;

Figure 11 shows that the trellis structure under the restriction of RLL (2,10) sign indicating number;

Figure 12 shows that the result who the 9th figure is done vertical arrangement;

Figure 13 shows that the 9th figure is done the vertically result of arrangement twice;

Figure 14 shows that with what first kind of retrogressive method separated trellis structure and concern corresponding diagram and recovering state circuit diagram;

Figure 15 shows that with what second kind of retrogressive method separated trellis structure and concern corresponding diagram and recovering state circuit diagram;

Figure 16 shows that with what the third retrogressive method was separated trellis structure and concern corresponding diagram and recovering state circuit diagram;

Figure 17 A is depicted as the circuit block diagram that retrogressive method uses register array;

Figure 17 B is depicted as the data flow of retrogressive method;

Figure 17 C is depicted as the another kind of data flow of retrogressive method; And

Figure 17 D is depicted as at serial data and adds the schematic diagram that dummy data postpones.

Label declaration in the accompanying drawing is as follows:

200: Viterbi decoder

202: the branch metric unit

204：ACS

206: the path internal storage location

502,504,506,508,1506,1508,1510: register array (register array)

1400,1500,1600,1712,1716,1718,1722: recovering state circuit (state retrievecircuit)

1402,1502,1602: decision circuitry (decision circuit)

1404,1504,1604: state

1406,1410,1506,1510,1606,1610: multiplexer (multiplexer)

1408,1508,1608: memory block (memory block)

1700: recall circuit (trace-back circuit)

1702: add-compare-selected cell (add-compare-select unit)

1704: data flow control (data string controller)

1714,1720: delay time register (delay register)

Embodiment

Figure 8 shows that the flow chart of the method for Viterbi decoder of the present invention.In Fig. 8, at first set up the trellis structure (S70) (as shown in Figure 3) that cooperates Viterbi decoder.For the bottleneck that solves ACS is that the trellis structure of Viterbi decoder is done reformation, and the method for reforming comprises horizontal arrangement and vertically puts dual mode in order.With original trellis structure shown in Fig. 9 A and n=2 is example, shown in Fig. 9 B original trellis structure is being done horizontal arrangement, so-called laterally arrangement is merged into a state with the trellis of original n state exactly, though the bottleneck of ACS exists equally, but it is nT that the time of bottleneck is elongated by 1T, and therefore the speed limit of whole Viterbi decoder also obtains to alleviate.

Shown in Fig. 9 C original trellis structure is done vertical arrangement.In Fig. 9 C, the trellis structure that cooperates Viterbi decoder is vertically put in order (S72).Because the vertical arrangement trellis structure that obtains by vertical arrangement, the index of the number meeting 2 of its state increases, the complexity that vertical arrangement trellis is attempted to change, can not occur so use RLL code to limit some state, vertically put trellis structure in order and obtain a run-length restriction trellis structure (S74) with computing.

The channel memory of as shown in figure 10 binary system input is that this channel is rather approximate with general common PRML channel shown in 3 the trellis structure.With the trellis structure under the restriction that RLL (2,10) sign indicating number is arranged shown in Figure 11 is example, and the trellis structure of Figure 10 is done RLL (2,10) yard restriction, can find that the trellis structure of Figure 11 has been simplified a lot.Shown in the result who Figure 11 is done vertical arrangement as shown in figure 12, the trellis structure of Figure 11 is done the restriction of vertical arrangement and RLL (2,10) sign indicating number, can find that each grade state number only increases to 2.Figure 11 is shown in the result who vertically puts in order for twice as shown in figure 13 done the restriction of vertically putting in order for twice with RLL (2,10) sign indicating number with the trellis structure of Figure 11, can find the too complexity that trellis structure does not become, but the bottleneck of ACS is significantly relaxed.

Then, at each bar branch in the trellis structure, Viterbi decoder can calculate branched measurement value (the branch metric unit 202 by Fig. 2 is carried out) (as Fig. 8 step S76).Secondly, vertically arrangement be with Viterbi decoder be considered as a finite state machine (Finite State Machine, FSM), by the characteristic of finite state machine as can be known:

Current output=function (current input and current state)

Following next state=function (current input and current state)

If state is redefined, new current state is regarded as " the current input of current state+script originally ", promptly input is originally absorbed in the state, then become:

Current output=only be the function of following next state

Following next state=function (current input and current state)

By Fig. 9 C as can be known, owing to becoming, trellis structure has current output=and only be the characteristic of the function of following next state, therefore (path candidate this moment (candidate path) meets on the same next state down when looking for the survival path, so their output signal will be the same), the bottleneck of ACS will disappear.Because, be connected this moment all branches on this state all have identical signal value (because current output=only be the function of next state down, and next state is identical down), so when calculating new path metric s (=old path metric s+ branch metric), path metric s that just can be older decides the magnitude relationship of new path metric.

Such way can continue to deduce, to reach the speed that any system needs, for example state is redefined one times of further expansion, new current state is regarded as " input of the current input+next time of present current state+present ", promptly the input of present input with next time absorbed in the state, becomes:

(current output; Output next time)=only be the function (as Fig. 8 step S78) of following next state

Following next state=function (input next time, current input and current state) (as Fig. 8 step S80)

With aforementioned be same reason, though the output under this situation becomes two, the path of determining all intersections remains the same at the signal value of this state.Above-mentioned way is that the further expansion by state reaches effect faster, makes the bottleneck of ACS more lax.

The method that the present embodiment proposition is recalled is to look for the optimal path of trellis structure with RLL code at deducing at Viterbi, and required path memory management mechanism is provided.As mentioned above, the operation principle of retrogressive method is exactly the judgement position of each state of record of first rule, and then recalls the merging point by these records.In fact, in the process of only recalling, can cause the ground of obscuring to need record (with reference to the step S82 of figure 8) just now.

Figure 14 shows that with what first kind of retrogressive method separated trellis structure and concern corresponding diagram and recovering state circuit diagram.In Figure 14, through the restriction of RLL code, along with the disappearance of some states, some branch has also disappeared.Its interconnected relationship of the state that remains becomes very clear and definite.For example, state " 1000 " must be from state " 1100 ", and is so online when not needing to be recorded in retrogressive method, also can obtain by clear and definite backstepping.

With Figure 14 is example, when the position judged in record (writing the action of (V)), need only use two cover internal memories rather than eight cover internal memories.When reading back record, (review (T), decoding (D)), decision circuitry 1402 in the recovering state circuit 1200 is got the state value of first three position of state 1404, judges the state value of current state 1404 and the relation of judging the position that is write down (judging promptly whether state value is legal state value) (with reference to the step S84 of figure 8).When the front three of state 1404 is " 000 " or " 111 ", indicate to judge, and continue to recall (with reference to the step S86 of figure 8) by the judgement position that precedence record gets off, first position as state 1404 is " 1 ", then a row data export multiplexer 1410 to above the multiplexer 1406 selection memory pieces 1408, and control multiplexers 1410 dateouts to state 1404 by decision circuitry 1402; First position as state 1404 is " 0 ", and then a row data export multiplexer 1410 to below the multiplexer 1406 selection memory pieces 1408, and control multiplexers 1410 dateouts to state 1404 by decision circuitry 1402.When the front three of state 1404 neither " 000 " neither " 111 " time, only need first position of extension state 1404 to get final product, first state value as state 1404 exports multiplexer 1410 to, and by decision circuitry 1402 control multiplexers 1410 dateouts to state 1404 to produce the state value of new state 1404.

Figure 15 shows that with what second kind of retrogressive method separated trellis structure to concern corresponding diagram and recovering state circuit diagram, shown in Figure 16 concern corresponding diagram and recovering state circuit diagram with what the third retrogressive method was separated trellis structure.Figure 15 and Figure 16 are respectively more complicated trellis structures, below describe Figure 15 and Figure 16 operation principle simply.

In Figure 15, decision circuitry 1502 in the recovering state circuit 1500 judge state 1504 the first two the position state value whether legal, it is legal to represent when the first two position of state 1504 is " 00 " or " 11 ", as state 1504 first with the 3rd position decision multiplexer 1506 selection memory pieces 1508 wherein a row data export multiplexer 1510 to, and by decision circuitry 1502 control multiplexers 1510 dateouts to state 1504.When the first two position of state 1504 neither " 00 " is represented neither " 11 " time illegal, twice of the state value of first of extension state 1504 and export multiplexer 1510 to then, and by decision circuitry 1502 control multiplexers 1510 dateouts to state 1504 to produce the state value of new state 1504.

In like manner, in Figure 16, decision circuitry 1602 in the recovering state circuit 1600 judge state 1604 first three the position state value whether legal, it is legal to represent when the front three of state 1604 is " 000 " or " 111 ", as state 1604 first, the 4th position and the 5th position decision multiplexer 1606 selection memory piece 1608 wherein a row data export multiplexer 1610 to, and by decision circuitry 1602 control multiplexers 1610 dateouts to state 1604.When the front three of state 1604 neither " 000 " is represented neither " 111 " time illegal, the state value of first of extension state 1604 and export multiplexer 1610 to then, and by decision circuitry 1602 control multiplexers 1610 dateouts to state 1604 to produce the state value of new state 1604.

Figure 17 A is depicted as the circuit block diagram that retrogressive method uses register array.In Figure 17 A, recall circuit 1700 and comprise and add-compare-selected cell 1702, in order to the optimal path of each state of computing and export one and judge the position.Data flow control 1704 adds-compares-judgement position that selected cell 1702 is exported in order to reception, and the decision output stream of judging the position to.Each judgement position that register array 1706 is exported in order to receiving data stream controller 1704, and shift out a previous judgement position from register array 1706, and do the action of reviewing to obtain a merging value.Register array 1708 or register array 1710 waiting register arrays 1706 are reviewed the merging value that obtains decoding, and, and shift out decoded judgement position to export as data.

Recovering state circuit 1712 is done bidirectional data transfers with register array 1706, and send data to delay time register 1714, the data that delay time register 1714 accepting state restore circuits 1712 are sent, and after postponing a period of time dateout to recovering state circuit 1716, the data that recovering state circuit 1716 receive delay registers 1714 are sent, and do bidirectional data transfers with register array 1710.Recovering state circuit 1718 is done bidirectional data transfers with register array 1706, and send data to delay time register 1720, the data that delay time register 1720 accepting state restore circuits 1718 are sent, and after postponing a period of time dateout to recovering state circuit 1722, the data that recovering state circuit 1722 receive delay registers 1720 are sent, and do bidirectional data transfers with register array 1708.

The data flow of the retrogressive method shown in Figure 17 B.In Figure 17 B, with reference to figure 17A, when the flow direction of data flow control 1704 control datas is during toward the left side, then register array 1710 is for waiting for (I) situation, register array 1708 is decoding (D) situation, register array 1708 when decoding and the past left side of the good data of will decode shift out (with reference to the step S94 of figure 8) stroke by stroke.Register array 1706 writes (V) judgement bit data stroke by stroke from the left side, and moved into register array 1708 toward the left side by the data that register array 1706 shifts out, when register array 1708 filled up the data of immigration, register array 1708 became wait (I) situation (with reference to the step S92 of figure 8) by decoding (D) situation.At this moment, register array 1706 is also done the action of reviewing (T), decodes with (with reference to the step S90 of figure 8) for register array 1710 to obtain merging point next time.

In like manner, the another kind of data flow of the retrogressive method shown in Figure 17 C.In Figure 17 C, with reference to figure 17A, when the flow direction of data flow control 1704 control datas is during toward the right, then register array 1708 is for waiting for (I) situation, register array 1710 is decoding (D) situation, register array 1710 when decoding and the past the right of the good data of will decode shift out (with reference to the step S94 of figure 8) stroke by stroke.Register array 1706 writes (V) judgement bit data stroke by stroke from the right, and moved into register array 1710 toward the right by the data that register array 1706 shifts out, when register array 1708 filled up the data of immigration, register array 1708 became wait (I) situation (with reference to the step S92 of figure 8) by decoding (D) situation.At this moment, register array 1706 is also done the action of reviewing (T), decodes with (with reference to the step S90 of figure 8) for register array 1708 to obtain merging point next time.

Schematic diagram shown in Figure 17 D in the delay of serial data adding dummy data.In Figure 17 A, for example, register array 1706 is given register array 1710 by recovering state circuit 1712, delay time register 1714 with recovering state circuit 1716 transmission data, can produce the data transfer delay phenomenon, must put into several dummy data (dummy) in register, the data that obtain of avoiding decoding produce error in data because of transmission delay.

Therefore, advantage of the present invention provides a kind of decoding circuit and method of Viterbi decoder, utilize RLL code effectively to solve trellis structure complicated trellis structure after vertically putting in order of Viterbi decoder, make ACS can parallelly carry out addition and comparison operation, and register array can have other action concurrently in the different time, so, ACS and PMU do not need a lot of register of quantity to come deal with data, similarly can reach the purpose of the decoding of high-speed vital ratio decoder.

In sum; though the present invention discloses as above with preferred embodiment; yet these preferred embodiments are not in order to limit the present invention; those skilled in the art can be without departing from the spirit and scope of the present invention; these embodiment are carried out various modifications and retouching, so protection scope of the present invention should be as the criterion with the scope that claims were defined.

Claims

1. A decoding method of a Viterbi decoder, the Viterbi decoder has a branch measurement unit, an addition-comparison-selection unit and a path memory unit, and the method comprises the following steps:

vertically sorting a trellis for matching the Viterbi decoder to obtain a vertically sorting trellis;

computing the longitudinal arrangement trellis according to a runlength-limited code to obtain a runlength-limited trellis;

the branch metric unit calculates a current input branch metric based on the run-length restricted trellis;

calculating the current input branch metric value, the next input branch metric value and a current state by the adding-comparing-selecting unit to obtain a next state value; and

Using the path memory unit to record the result calculated by the add-comparison-select unit to obtain a surviving path, and decoding the recorded surviving path.

2. The decoding method of the Viterbi decoder as claimed in claim 1, wherein the trellis diagram matching the Viterbi decoder is firstly established before vertical sorting.

3. The decoding method of the Viterbi decoder as claimed in claim 2, wherein the trellis diagram matching the Viterbi decoder is vertically arranged by adopting multiple vertical arrangement methods.

4. The decoding method of a Viterbi decoder as claimed in claim 3, wherein a current output judgment bit and a next output judgment bit are set by the addition-comparison-selection unit only according to the next state value.

5. The decoding method of the Viterbi decoder as claimed in claim 4, wherein the branch metric value calculated according to the run-length limited trellis is input to the adding-comparing-selecting unit to become the One of the current input branch metric value and the next input branch metric value.

6 . The decoding method of a Viterbi decoder as claimed in claim 5 , wherein the method for recording the surviving paths in the path memory unit uses one of a hybrid exchange method and a backtracking method. 7 .

7. the decoding method of Viterbi decoder as claimed in claim 6, wherein said mixed exchange method is to be equipped with a set of internal memory for each state of the described trellis diagram that cooperates described Viterbi decoder, to be used for Record the surviving paths to this state value.

8. The decoding method of Viterbi decoder as claimed in claim 6, wherein said backtracking method also comprises the following steps:

According to the current output judgment bit and the next output judgment bit, record a last state value and a judgment bit of the current state value;

judging the relationship between the current state value and the judging bit;

Writing the judgment bit into an appropriate state value;

When not recording the state of the judgment bit, then write an extension bit identical to the first bit of the state to the state;

sending the judgment bit to a retrospectively written register array, and retrospectively obtaining a merged value;

When the judgment bits stored in a decoding register array reach a predetermined number, the decoding register array becomes a waiting register array; and

Decoding the judgment bit originally stored in the waiting register array according to the merged value.

9. A decoding method of a Viterbi decoder, the Viterbi decoder has a branch measurement unit, an addition-comparison-selection unit and a path memory unit, the path memory unit includes a decoding register array, a retroactive write register array and a waiting register array, the steps of the method include:

creating a trellis diagram for said Viterbi decoder;

performing vertical arrangement on the trellis diagram matching the Viterbi to obtain a longitudinal arrangement trellis diagram;

the branch metric unit calculates a branch metric value according to the run-length limited trellis;

calculating a current input branch metric value, a next input branch metric value and a current state value by the addition-comparison-selection unit to obtain a next state value;

The addition-comparison-selection unit only sets a current output judgment bit and a next output judgment bit according to the next state value;

Recording a last state value and a judgment bit on the current state value according to the current output judgment bit and the next output judgment bit;

judging the relationship between the current state and the judging bit;

Writing the judgment bit into an appropriate state value;

Sending the judgment bit to the trace write register array by the add-comparison-select unit, and obtain a combined value retroactively;

When the judgment bits stored in the decoding register array reach a predetermined number, the decoding register array becomes the waiting register array; and

10. The decoding method of the Viterbi decoder as claimed in claim 9, wherein the trellis diagram matched with the Viterbi decoder is vertically sorted by adopting multiple vertical sorting methods.

11. The decoding method of the Viterbi decoder as claimed in claim 10, wherein the branch metric calculated according to the run-length limited trellis is input to the adding-comparing-selecting unit to become the One of the current input branch metric and the next input branch metric.

12. A decoding circuit of a Viterbi decoder, the decoding circuit has a branch metric unit, an addition-comparison-selection unit and a path memory unit, the branch metric unit is used to calculate a branch metric value, and output the The branch metric value is sent to the add-comparison-selection unit, the add-comparison-selection unit calculates the optimal path of a state value according to the branch metric value, and outputs a judgment bit, and the path memory unit includes :

a data flow controller, used to receive the judgment bit output by the addition-comparison-selection unit, and determine the output flow direction of the judgment bit;

Retroactively write to the register array, receive the judgment bit output by the data flow controller, and retroactively obtain a combined value;

an array of waiting registers for decoding said merged value traced back to said write-back register array; and

A decoding register array, decoding the judging bits stored in the decoding register array according to the combined value obtained retrospectively.

13. The decoding circuit of a Viterbi decoder as claimed in claim 12, wherein when the judgment bits stored in the decoding register array reach a predetermined number, the decoding register array becomes the waiting register array.

14. The decoding circuit of the Viterbi decoder as claimed in claim 13, wherein when the retrospective write register array obtains the combined value and provides it to the waiting register array, the waiting register array becomes the The register array is decoded and decoded based on the merged value.

15. The decoding circuit of the Viterbi decoder as claimed in claim 14, further comprising:

A first state recovery circuit, which performs bidirectional data transmission with the traceable write register array, and can send data;

a first delay register, receiving the data sent by the first state restoration circuit, and outputting the data after a delay; and

A second state recovery circuit receives the data sent by the first delay register, and performs bidirectional data transmission with the waiting register array.

16. The decoding circuit of the Viterbi decoder as claimed in claim 14, further comprising:

A third state recovery circuit, which performs two-way data transmission with the traceable write register array, and can send data;

A second delay register, receiving the data sent by the third state recovery circuit, and outputting the data after a period of delay; and

A fourth state restoration circuit, receiving the data sent by the second delay register, and performing bidirectional data transmission with the decoding register array.

17. The decoding circuit of Viterbi decoder as claimed in claim 16, wherein said first state restoration circuit performs data access with a memory block and a state register in said register array, and said first state restoration circuit The circuit also includes:

A first judging circuit, having a plurality of judging signal input terminals capable of receiving the data output by the status register, and having a selection signal output terminal capable of outputting a selection signal;

a first multiplexer having a plurality of input terminals capable of receiving data of the memory block, having a selection terminal capable of receiving data of the status register, and having an output terminal capable of outputting data; and

A second multiplexer, with an input end that can receive the data output by the status register and the output end of the first multiplexer, and a selection end that can receive the output of the first judgment circuit The selection signal output by the selection signal output end has an output end capable of outputting data to the status register.

18. The decoding circuit of the Viterbi decoder as claimed in claim 16, wherein the second state recovery circuit performs data access with the memory block and the state register in the register array, and the second The state restoration circuit also includes:

A second judging circuit, having a judging signal input end capable of receiving the data output by the state register, and having a selection signal output end capable of outputting the selection signal;

A third multiplexer, having an input terminal capable of receiving data from the memory block, having a selection terminal capable of receiving data from the status register, and having an output terminal capable of outputting data; and

A fourth multiplexer, with an input end that can receive the data output by the status register and the output end of the third multiplexer, and a selection end that can receive the output of the second judgment circuit The selection signal output from the selection signal output terminal has an output terminal that outputs data to the status register.

19. The decoding circuit of the Viterbi decoder as claimed in claim 16, wherein said third state recovery circuit performs data access with said memory block and said state register in said register array, said third The state restoration circuit also includes:

A third judging circuit, having a judging signal input terminal capable of receiving the data output by the state register, and having a selection signal output terminal capable of outputting the selection signal;

a fifth multiplexer having inputs capable of receiving data from the memory block, select ends capable of receiving data from the status register, and output ends capable of outputting data; and

A sixth multiplexer, with an input end that can receive the data output by the status register and the output end of the fifth multiplexer, and a selection end that can receive the data of the third judging circuit The selection signal output from the selection signal output terminal has an output terminal that outputs data to the status register.

20. The decoding circuit of the Viterbi decoder as claimed in claim 16, wherein said fourth state recovery circuit performs data access with said memory block and said state register in said register array, said fourth The state restoration circuit also includes:

A fourth judging circuit, having a judging signal input end capable of receiving the data output by the state register, and having a selection signal output end capable of outputting the selection signal;

A seventh multiplexer having an input end capable of receiving data from the memory block, a select end capable of receiving data from the status register, and an output end capable of outputting data; and

An eighth multiplexer, which has some input terminals that can receive the data output by the status register and the output terminal of the seventh multiplexer, and has a selection terminal that can receive the fourth judgment circuit The selection signal is output by the selection signal output terminal, and has an output terminal capable of outputting data to the status register.