Path trace viterbi decoder

Claim 2

A viterbi decoder comprising: a branch metric calculator for calculating branch metrics for every node on the basis of a received signal; a path selecting unit selecting a surviving.path for every node on the basis of path metrics calculated on the basis of the branch metrics from the branch metric calculator to output path selecting signals indicating the surviving paths respectively; a path memory for storing said path selecting signals generated by the path selecting unit for every node; a node calculator for tracing the most likely path by repeating a calculation in which a previous node with respect to a given node is calculated on the basis of the node number of the given node and the path selecting signal corresponding to the given node; and a trace memory for storing the most likely path data generated by the node calculator; wherein the most likely path data in the trace memory is updated on the basis of the calculated result of the node calculator; and a decoded signal is generated on the basis of the most likely path data stored in the trace memory.

Claim 3

A viterbi decoder comprising: a branch metric calculator for calculating branch metrics for every node on the basis of a received signal; , a path selecting unit for selecting a surviving path for every node on the basis of path metrics calculated on the basis of the branch metrics from the branch metric calculutor to output path selecting signals indicating the surviving paths respectively; a path memory for storing said path selecting signals generated by the path selecting unit for every node; a node calculator for tracing a most likely path by repeating a calculation in which a previous node with respect to a given node is calculated on the basis of the node number of the given node and the path selecting signal corresponding to the given node; a trace memory for storing the most likely path data generated by the node calculator over the path history length; and a coincidence comparator for comparing the node data calculated by the node calculator with the most likely path node data already stored in the trace memory to detect a coincidence therebetween, thereby detecting the coincidence between the most likely path newly traced by the node calculator and the previous most likely path already stored in the trace memory; wherein the trace operation by the node calculator is terminated in response to the detection of the coincidence by the coincidence comparator to start the tracing of the new most likely path; the previous most likely path data stored in the trace memory is updated in accordance with the node data traced by the node calculator to produce the new most likely path data; and a decoded signal is generated on the basis of the most likely path data stored in the trace memory.

Claim 4

A viterbi decoder comprising: a branch metric calculator for calculating branch metrics for every node on the basis of a received signal; , a path selecting unit for selecting a surviving path for every node on the basis of path metrics calculated on the basis of the branch metrics from the branch metric calculutor to output path selecting signals indicating the surviving paths respectively; a path memory for storing said path selecting signals generated by the path selecting unit for every node; a node calculator for tracing a most likely path by repeating a calculation in which a previous node with respect to a given node is calculated on the basis of the node number of the given node and the path selecting signal corresponding to the given node; a trace memory for storing the most likely path data generated by the node calculator over the path history length; and a coincidence comparator for comparing the node data calculated by the node calculator with the most likely path node data already stored in the trace memory to detect a coincidence therebetween, thereby detecting the coincidence between the most likely path newly traced by the node calculator and the previous most likely path already stored in the trace memory; wherein the trace operation by the node calculator is terminated in response to the detection of the coincidence by the coincidence comparator to start the tracing of the new most likely path; the previous most likely path data stored in the trace memory is updated in accordance with the node data traced by the node calculator to produce the new most likely path data; and a decoded signal is generated on the basis of the most likely path data stored in the trace memory.

Claim 5

A viterbi decoder comprising: a branch metric calculator for calculating branch metrics for every node on the basis of a received signal; a path selecting unit for selecting a surviving path for every node on the basis of path metrics calculated on the basis of the branch metrics from the branch metric calculator to output path selecting signals indicating the surviving paths respectively; a path memory for storing said path selecting signals generated by the path selecting unit for every node; a node calculator for tracing a most likely path by repeating a calculation in which a previous node with respect to a given node is calculated on the basis of the node number of the given node and the path selecting signal corresponding to the given node; a trace memory for storing the most likely path data generated by the node calculator over the path history length; a coincidence comparator for comparing the node data calculated by the node calculator with the most likely path node data already stored in the trace memory to detect a coincidence therebetween, thereby detecting the coincidence between the most likely path newly traced by the node calculator and the previous most likely path already stored in the trace memory; wherein a decoded signal is generated on the basis of the most likely path data stored in the trace memory and a given node data is added to a head position of the most likely path data stored in the trace memory, at every decoding cycle having a period smaller than a period for tracing the most likely path over the path history length; the previous most likely path data stored in the trace memory is updated in accordance with the node data traced by the node calculator to produce the new most likely path data; and the tracing is terminated, when the coincidence is detected by the coincidence comparator within one decoding cycle, to restart the tracing of the new most likely path in the following decoding cycle, and when the coincidence is not detected, is continued in the following decoding cycle.

Claim 6

A viterbi decoder comprising: a branch metric calculator for calculating branch metrics for every node on the basis of a received signal; a path selecting unit for selecting a surviving path for every node on the basis of path metrics calculated on the basis of the branch metrics from the branch metric calculator to output path selecting signals indicating the surviving paths respectively; a path memory for storing said path selecting signals generated by the path selecting unit for every node; a node calculator for tracing a most likely path by repeating a calculation in which a previous node with respect to a given node is calculated on the basis of the node number of the given node and the path selecting signal corresponding to the given node; a trace memory for storing the most likely path data generated by the node calculator over the path history length; a coincidence comparator for comparing the node data calculated by the node calculator with the most likely path node data already stored in the trace memory to detect a coincidence therebetween, thereby detecting the coincidence between the most likely path newly traced by the node calculator and the previous most likely path already stored in the trace memory; wherein a decoded signal is generated on the basis of the most likely path data stored in the trace memory and a given node data is added to a head position of the most likely path data stored in the trace memory, at every decoding cycle having a period smaller than a period for tracing the most likely path over the path history length; the previous most likely path data stored in the trace memory is updated in accordance with the node data traced by the node calculator to produce the new most likely path data; and the tracing is terminated, when the coincidence is detected by the coincidence comparator within one decoding cycle, to restart the tracing of the new most likely path in the following decoding cycle, and when the coincidence is not detected, is continued in the following decoding cycle.

Claim 7

A viterbi decoder in accordance with claim 3, wherein: the decoding cycle comprises an input-output state and a plurality of trace states, the read operation of the node data from the trace memory to generate the decoded signal and the write operation of the given node data to the head position of the most likely path data stored in the trace memory are carried out in the input-output state, the write operation of the node data calculated by the node calculator to the trace memory is carried out in each trace state.

Claim 8

A viterbi decoder in accordance with claim 4, wherein the coincidence comparator carries out the comparison for detecting the coincidence for every trace state in the decoding cycle.

Claim 9

A viterbi decoder in accordance with claim 4, wherein the coincidence comparator carries out the comparison for detecting the coincidence only for the last trace state in the decoding cycle.

Claim 10

A viterbi decoder in accordance with claim 6, wherein the read operation of the node data from the trace memory for the comparison is carried out at the last trace state of the decoding cycle.

Claim 11

A viterbi decoder in accordance with claim 6, wherein the read operation of the node data from the trace memory for the comparison is carried out at the first trace state of the decoding cycle.

Claim 12

A viterbi decoder in accordance with claim 3 further comprising a node determining unit for determining a minimum path metric node on the basis of the path metrics calculated by the path selecting unit; wherein the minimum path metric node determined by the node determining unit is used as the trace starting node of the most likely path.

Claim 13

A viterbi decoder in accordance with claim 9, wherein if the tracing of the most likely path is not terminated within one decoding cycle and continued in other decoding cycles thereafter, the minimum path metric node for the other decoding cycles which follow the first decoding cycle is used in sequence as the trace starting node of the new most likely path after the coincidence is detected.

Claim 14

A viterbi decoder in accordance with claim 9, wherein if the tracing of the most likely path is not terminated within one decoding cycle and continued in other decoding cycles thereafter, the minimum path metric node number is used as the given node number which is added to the head position of the most likely path data stored in the trace memory in the decoding cycle where the tracing is continued, and the minimum path metric node for the decoding cycle where the tracing is newly restarted is used as the trace starting node of the new most likely path after the coincidence is detected.

Claim 15

A viterbi decoder in accordance with claim 9, wherein if the tracing of the most likely path is not terminated within one decoding cycle and continued in other decording cycles thereafter, a dummy node number which does not exist is used as the given node number which is added to the head position of the most likely path data stored in the trace memory in the decoding cycle where the tracing is continued, and the minimum path metric node for the decoding cycle where the tracing is newly restarted is used as the trace starting node on the new most likely path after the coincidence is detected.

Claim 16

A viterbi decoder comprising: a branch metric calculator for calculating branch metrics for every node on the basis of a received signal; a path selecting unit for selecting a surviving path for each node on the basis of path metrics calculated on the basis of the branch metrics from the branch metric circuit to output path selecting signals indicating the surviving path respectively; a path memory for storing said path selecting signals generated by the path selecting unit for each node; a node calculator for tracing a most likely path by repeating a calculation in which a previous node with respect to a given node is calculated on the basis of the node number of the given node and the path selecting signal corresponding to the given node; and a trace memory for storing the most likely path data generated by the node calculator; wherein the most likely path data in the trace memory is updated on the basis of the calculated result of the node calculator; a tracing period for tracing the most likely path over one path history length is divided by a plurality of decoding cycles; a decoded signal is generated on the basis of the most likely path data stored in the trace memory, and a given node data is added to the head position of the most likely path data stored in the trace memory, at every decoding cycle.

Claim 17

A viterbi decoder comprising: a branch metric calculator for calculating branch metrics for every node on the basis of a received signal; a path selecting unit for selecting a surviving path for each node on the basis of path metrics calculated on the basis of the branch metrics from the branch metric circuit to output path selecting signals indicating the surviving path respectively; a path memory for storing said path selecting signals generated by the path selecting unit for each node; a node calculator for tracing a most likely path by repeating a calculation in which a previous node with respect to a given node is calculated on the basis of the node number of the given node and the path selecting signal corresponding to the given node; and a trace memory for storing the most likely path data generated by the node calculator; wherein the most likely path data in the trace memory is updated on the basis of the calculated result of the node calculator; a tracing period for tracing the most likely path over one path history length is divided by a plurality of decoding cycles; a decoded signal is generated on the basis of the most likely path data stored in the trace memory, and a given node data is added to the head position of the most likely path data stored in the trace memory, at every decoding cycle.

Claim 18

A viterbi decoder in accordance with claim 13, further comprising: a minimum path metric node determining unit for determining a minimum path metric node on the basis of the path metrics of each node calculated by the path selecting unit; a detecting unit for detecting a completion of tracing of the most likely path over one history length; and a trace control unit for restarting the new path tracing from the trace starting node which is set to the minimum path metric node determined by the minimum path metric node determining unit when the completion of the previous path tracing-is detected by the detecting unit.

Claim 19

A viterbi decoder in accordance with claim 14, wherein the addressing for the trace memory can be carried out to circulate in both increment and decrement directions of the trace memory, the write operation of the most likely path data and the write operation of the given node data for the trace memory are in opposite directions; an address coincidence detecting unit for detecting a coincidence of the address in both addressing directions is provided, and when the coincidence is detected by the address coincidence detecting unit, the tracing is terminated to start the tracing of the new most likely path.

Claim 20

A viterbi decoder in accordance with claim 13, wherein the addressing for the trace memory can be carried out to circulate in both increment and decrement directions of the trace memory, the write operation of the most likely path data and the write operation of the given node data for the trace memory are in opposite directions and are carried out non-correlatively, and the length of the trace memory is longer than usual.

Claim 21

A viterbi decoder in accordance with claim 14, wherein the length of the trace memory is at least the number of times of stages corresponding the number of times of decoding cycle during the period for tracing one most likely path, and the final side node data of the most likely path is stored in the trace memory at the time of the completion of the tracing of one most likely path.

Claim 22

A viterbi decoder in accordance with claim 9, wherein if the tracing of the most likely path is not terminated within one decoding cycle and continued in another decoding cycle thereafter, a dummy node number which does not exist is used as the given node number added to the head position of the most likely path data stored.in the trace memory in the decoding cycle where the tracing is continued, and when the following new most likely path is traced, the node data calculated by the node calculator is not compared with the most likely path node data already stored in the trace memory but merely written into the trace memory at the head side portion of the most likely path in which the dummy node number is written.

Claim 23

A viterbi decoder in accordance with claim 1, wherein the decoded signal is obtained from a most significant bit of the final level node number, represented by a binary notation, of the most likely path.