CN100477534C - Decode circuit and method of wittbi decoder - Google Patents
Decode circuit and method of wittbi decoder Download PDFInfo
- Publication number
- CN100477534C CN100477534C CNB021305323A CN02130532A CN100477534C CN 100477534 C CN100477534 C CN 100477534C CN B021305323 A CNB021305323 A CN B021305323A CN 02130532 A CN02130532 A CN 02130532A CN 100477534 C CN100477534 C CN 100477534C
- Authority
- CN
- China
- Prior art keywords
- data
- register array
- state
- viterbi decoder
- register
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Images
Landscapes
- Error Detection And Correction (AREA)
Abstract
The circuit comprises a branch measuring unit, an adding-comparing-selecting unit and a path memory unit which consists of a retroaction write in register array, a wait register array and a decoding register array. The run length limited code is used to solve complex cellular drawing after Witt ratio decoder cellular drawing is longitudinal-ordered and the register array can undertake some other actions at different time so it is unnecessary to use many registers to process data, but decoding aim by using high-speed Witt ratio decoder can also be achieved.
Description
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
1* " in the previous input of first internal memory "+k
2* " in the previous input of second internal memory ")
In Figure 1A, k
1With k
2Reflect the characteristic of this channel in the enforcement, k
1With k
2Value 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
1With k
2Value, 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
1With k
2Determine 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)]
2Or | 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 2TPass through State again
00 at 3TArrive State at last
00 at 4TThis 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 1TShould 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 1TThe 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 2TThe survival path be how by from State
00 at 1TThe survival path with from State
00 at 1TThe survival path pick out, with reference to figure 3, at State
00 at 2TSurvivormetric SM
00 at 2TBe 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 (20)
1. the coding/decoding method of a Viterbi decoder, this Viterbi decoder has a branch metric unit, and adds-compare-selected cell and a path internal storage location, and described method comprises the following steps:
A trellis structure that cooperates described Viterbi decoder is vertically put in order, vertically put in order trellis structure to obtain one;
According to the described vertical arrangement trellis structure of a RLL code computing, to obtain a run-length restriction trellis structure;
According to described run-length restriction trellis structure, described branch metric unit calculates a current input branched measurement value;
By described adding-compare-selected cell calculate described current input branched measurement value, one next time an input branched measurement value and current state, to obtain next state value; And
Write down described adding-compare-selected cell institute result calculated with described path internal storage location,, decoded in the described survival path that record is finished to obtain a survival path.
2. the coding/decoding method of Viterbi decoder as claimed in claim 1 was wherein set up the described trellis structure that cooperates described Viterbi decoder earlier before vertically putting in order.
3. the coding/decoding method of Viterbi decoder as claimed in claim 2 wherein adopts repeatedly vertical Collator Mode will cooperate the described trellis structure of described Viterbi decoder to do vertical arrangement.
4. the coding/decoding method of Viterbi decoder as claimed in claim 3 is wherein only set a current output according to described next state value by described adding-compare-selected cell and is judged that position and next time output judges the position.
5. the coding/decoding method of Viterbi decoder as claimed in claim 4, wherein the described branched measurement value that is calculated according to described run-length restriction trellis structure inputs to described adding-compares-selected cell, to become described current input branched measurement value and described next time input branched measurement value the two one of them.
6. the coding/decoding method of Viterbi decoder as claimed in claim 5, wherein said path internal storage location write down described survival route method and use one to mix exchange process and a backtracking method the two one of them.
7. the coding/decoding method of Viterbi decoder as claimed in claim 6, wherein said mixing exchange process is each state outfit one cover internal memory for the described trellis structure that cooperates described Viterbi decoder, to be used for writing down the described survival path that arrives this state value.
8. the coding/decoding method of Viterbi decoder as claimed in claim 6, wherein said backtracking method also comprises the following steps:
Judge the judgement of a state value that position and described output next time judges position record last time and current described state value according to described current output;
Judge current described state value and the described relation of judging the position;
Described judgement position is write suitable described state value;
When not being the described described state of judging the position of record, then write first identical extension bit with described state to described state;
Send described judgement position and review to one and write register array, and review and obtain a merging value;
The described judgement position that is stored in a codec register array is during to predetermined quantity, and described codec register array becomes one and waits for register array; And
According to the stored described judgement position of the original described waiting register array of described merging value decoding.
9. the coding/decoding method of a Viterbi decoder, this Viterbi decoder has a branch metric unit, and adds-compare-selected cell and a path internal storage location, this path internal storage location comprises that a codec register array, is reviewed and writes register array and and wait for register array that the step of described method comprises:
Set up a trellis structure that cooperates described Viterbi decoder;
To cooperate the described trellis structure of described Viterbi vertically to put in order, vertically put trellis structure in order to obtain one;
According to the described vertical arrangement trellis structure of a RLL code computing, to obtain a run-length restriction trellis structure;
According to described run-length restriction trellis structure, described branch metric unit calculates a branched measurement value;
By described adding-compare-selected cell calculate a current input branched measurement value, one next time an input branched measurement value and current state value, to obtain next state value;
Only set a current output by described adding-compare-selected cell and judge that position and next time output judges the position according to described next state value;
Judge a judgement on a state value that position and described output next time judges position record last time and the current described state value according to described current output;
Judge current described state and the described relation of judging the position;
Described judgement position is write suitable described state value;
Send described judgement position to described reviewing by described adding-compare-selected cell and write register array, and review and obtain a merging value;
The described judgement position that is stored in described codec register array is during to predetermined quantity, and described codec register array becomes described waiting register array; And
According to the stored described judgement position of the original described waiting register array of described merging value decoding.
10. the coding/decoding method of Viterbi decoder as claimed in claim 9 wherein adopts repeatedly vertical Collator Mode will cooperate the described trellis structure of described Viterbi decoder to do vertical arrangement.
11. the coding/decoding method of Viterbi decoder as claimed in claim 10, wherein calculate described branched measurement value and input to described adding-compare-selected cell, to become described current input branched measurement value and described next time input branched measurement value the two one of them according to described run-length restriction trellis structure.
12. the decoding circuit of a Viterbi decoder, this decoding circuit has a branch metric unit, and adds-compare-selected cell and a path internal storage location, described branch metric unit is in order to calculate a branched measurement value, and export described branched measurement value to described adding-compare-selected cell, described adding-compare-selected cell is according to the optimal path of described branched measurement value with computing one state value, and export one and judge the position, described path internal storage location comprises:
One data flow control, in order to receiving the described judgement position that described adding-compare-selected cell is exported, and determine the described output stream of judging the position to;
One reviews and writes register array, receives the described judgement position that described data flow control is exported, and reviews and obtain a merging value;
One waits for register array, and described reviewing write register array and review the described merging value that obtains to decode; And
One codec register array is decoded according to reviewing the described judgement position that the described merging value that obtains will be stored in described codec register array.
13. the decoding circuit of Viterbi decoder as claimed in claim 12, when the stored described judgement position of wherein said codec register array reached predetermined quantity, described codec register array became described waiting register array.
14. the decoding circuit of Viterbi decoder as claimed in claim 13, wherein ought describedly review and write register array and review and obtain described merging value and offer described waiting register array, described waiting register array becomes described codec register array, and decodes according to described merging value.
15. the decoding circuit of Viterbi decoder as claimed in claim 14, wherein said review to write between register array and the described waiting register array also comprise:
One first recovering state circuit writes register array and carries out bidirectional data transfers with described reviewing, and can send data;
One first delay time register receives the data that the described first recovering state circuit is sent, and dateout after postponing a period of time; And
One second recovering state circuit receives the data that described first delay time register is sent, and carries out bidirectional data transfers with described waiting register array.
16. the decoding circuit of Viterbi decoder as claimed in claim 14, wherein said review to write between register array and the described codec register array also comprise:
One third state restore circuit writes register array and carries out bidirectional data transfers with described reviewing, and can send data;
One second delay time register receives the data that described third state restore circuit is sent, and dateout after postponing a period of time; And
One four condition restore circuit receives the data that described second delay time register is sent, and carries out bidirectional data transfers with described codec register array.
17. the decoding circuit of Viterbi decoder as claimed in claim 16, a memory block and a status register in wherein said first recovering state circuit and the described register array are done data access, and the described first recovering state circuit also comprises:
One first decision circuitry has a plurality of judgement signal input parts and can receive the data that described status register is exported, and has the exportable selection signal of a selection signal output part;
One first multiplexer has the data that a plurality of inputs can receive described memory block, has a selecting side and can receive described mode register data, and have the exportable data of an output; And
One second multiplexer, have input and can receive the data that the described output of described status register and described first multiplexer is exported, have the selecting side and can receive the described selection signal that the described selection signal output part of described first decision circuitry is exported, and have the exportable data of output to described status register.
18. the decoding circuit of Viterbi decoder as claimed in claim 16, described memory block and described status register in wherein said second recovering state circuit and the described register array carry out data access, and the described second recovering state circuit also comprises:
One second decision circuitry has the signal input part of judgement and can receive the data that described status register is exported, and has the exportable described selection signal of the signal output part of selection;
One the 3rd multiplexer has the data that input can receive described memory block, has the selecting side and can receive described mode register data, and have the exportable data of output; And
One the 4th multiplexer, have input and can receive the data that the described output of described status register and described the 3rd multiplexer is exported, have the selecting side and can receive the described selection signal that the described selection signal output part of described second decision circuitry is exported, and have the output dateout to described status register.
19. the decoding circuit of Viterbi decoder as claimed in claim 16, described memory block and described status register in wherein said third state restore circuit and the described register array carry out data access, and described third state restore circuit also comprises:
One the 3rd decision circuitry has the signal input part of judgement and can receive the data that described status register is exported, and has the exportable described selection signal of the signal output part of selection;
One the 5th multiplexer has the data that a little inputs can receive described memory block, has the selecting side and can receive described mode register data, and have the exportable data of output; And
One the 6th multiplexer, have input and can receive the data that the described output of described status register and described the 5th multiplexer is exported, have the selecting side and can receive the described selection signal that the described selection signal output part of described the 3rd decision circuitry is exported, and have the output dateout to described status register.
20. the decoding circuit of Viterbi decoder as claimed in claim 16, described memory block and described status register in wherein said four condition restore circuit and the described register array carry out data access, and described four condition restore circuit also comprises:
One the 4th decision circuitry has the signal input part of judgement and can receive the data that described status register is exported, and has the exportable described selection signal of the signal output part of selection;
One the 7th multiplexer has the data that input can receive described memory block, has the selecting side and can receive described mode register data, and have the exportable data of output; And
One the 8th multiplexer, have a little inputs and can receive the data that the described output of described status register and described the 7th multiplexer is exported, have the selecting side and can receive the described selection signal that the described selection signal output part of described the 4th decision circuitry is exported, and have the exportable data of output to described status register.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB021305323A CN100477534C (en) | 2002-08-14 | 2002-08-14 | Decode circuit and method of wittbi decoder |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB021305323A CN100477534C (en) | 2002-08-14 | 2002-08-14 | Decode circuit and method of wittbi decoder |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1476176A CN1476176A (en) | 2004-02-18 |
| CN100477534C true CN100477534C (en) | 2009-04-08 |
Family
ID=34144505
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB021305323A Expired - Lifetime CN100477534C (en) | 2002-08-14 | 2002-08-14 | Decode circuit and method of wittbi decoder |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN100477534C (en) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB0504483D0 (en) * | 2005-03-03 | 2005-04-13 | Ttp Communications Ltd | Trellis calculations |
| CN101390293B (en) * | 2005-12-22 | 2011-06-08 | 创达特（苏州）科技有限责任公司 | A four-stage parallel processing based vdsl2 viterbi decoder |
| US8300739B2 (en) * | 2009-04-21 | 2012-10-30 | Telefonaktiebolaget L M Ericsson (Publ) | Method and apparatus for generating soft bit values in reduced-state equalizers |
| TWI729755B (en) * | 2020-04-01 | 2021-06-01 | 智原科技股份有限公司 | Receiver and internal tcm decoder and associated decoding method |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1142143A (en) * | 1995-06-30 | 1997-02-05 | 现代电子产业株式会社 | Decoder |
| CN1281296A (en) * | 1999-07-15 | 2001-01-24 | 富士通株式会社 | Weitebi decoder and transmission equipment |
| US6324226B1 (en) * | 1999-11-22 | 2001-11-27 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder |
| US6351839B1 (en) * | 1998-01-22 | 2002-02-26 | Lg Information & Communications, Ltd. | State metric memory of viterbi decoder and its decoding method |
| JP3266182B2 (en) * | 1997-06-10 | 2002-03-18 | 日本電気株式会社 | Viterbi decoder |
-
2002
- 2002-08-14 CN CNB021305323A patent/CN100477534C/en not_active Expired - Lifetime
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1142143A (en) * | 1995-06-30 | 1997-02-05 | 现代电子产业株式会社 | Decoder |
| JP3266182B2 (en) * | 1997-06-10 | 2002-03-18 | 日本電気株式会社 | Viterbi decoder |
| US6351839B1 (en) * | 1998-01-22 | 2002-02-26 | Lg Information & Communications, Ltd. | State metric memory of viterbi decoder and its decoding method |
| CN1281296A (en) * | 1999-07-15 | 2001-01-24 | 富士通株式会社 | Weitebi decoder and transmission equipment |
| US6324226B1 (en) * | 1999-11-22 | 2001-11-27 | Matsushita Electric Industrial Co., Ltd. | Viterbi decoder |
Also Published As
| Publication number | Publication date |
|---|---|
| CN1476176A (en) | 2004-02-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4905317A (en) | Path memory control method in Viterbi decoder | |
| KR100426712B1 (en) | Viterbi decoder | |
| CA1248236A (en) | Viterbi decoder with the pipeline processing function | |
| JP2693256B2 (en) | Viterbi equalizer for recording device and recording device | |
| KR19990063227A (en) | Viterbi decoding device and Viterbi decoding method | |
| KR20060087452A (en) | Method and apparatus for soft-output viterbi detection using a multiple-step trellis | |
| US6041433A (en) | Viterbi decoder and viterbi decoding method | |
| US8375281B2 (en) | Method and apparatus for storing survivor paths in a viterbi detector using systematic pointer exchange | |
| KR100197633B1 (en) | Survivor memory in viterbi decoder using trace-delete method | |
| CN100477534C (en) | Decode circuit and method of wittbi decoder | |
| US20060072687A1 (en) | Decoding circuit and decoding method for a Viterbi decoder | |
| US7127667B2 (en) | ACS circuit and viterbi decoder with the circuit | |
| JP3266182B2 (en) | Viterbi decoder | |
| US5996112A (en) | Area-efficient surviving paths unit for Viterbi decoders | |
| US5878060A (en) | Viterbi decoding apparatus and viterbe decoding method | |
| US5828675A (en) | Viterbi decoder circuit | |
| JP3242059B2 (en) | Viterbi decoder | |
| JPH0951278A (en) | Viterbi decoder | |
| US7120855B2 (en) | Survivor path memory circuit and Viterbi decoder with the same | |
| US7590926B2 (en) | Decoding apparatus, decoding method, program-recording medium, program and recording/reproduction apparatus | |
| US8032818B2 (en) | Method and apparatus for storing survivor paths in a Viterbi detector using input-dependent pointer exchange | |
| JP3260714B2 (en) | Viterbi decoding device and Viterbi decoding method | |
| JP4324195B2 (en) | Path memory circuit | |
| US20070230606A1 (en) | Viterbi traceback | |
| JPH0361375B2 (en) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CX01 | Expiry of patent term | ||
| CX01 | Expiry of patent term |
Granted publication date: 20090408 |