Path trace viterbi decoder

Claim 2

A Viterbi decoder for decoding a received signal, and having a plurality of nodes, each corresponding to a state of said decoder, comprising: branch metric calculator means for calculating branch metrics for each of the nodes on the basis of the received signal; path metric calculator means for calculating path metrics on the basis of said branch metrics; path selecting means for selecting a surviving path metric for each of the nodes on the basis of said path metrics and for providing path selecting signals indicating the surviving paths; path memory means for storing said path selecting signals generated by said path selecting means for each of the nodes; node calculator means for determining a node of a most likely path based on one of said path selecting signals and a previously determined node; trace memory means for storing said nodes, corresponding to the most likely path data, generated by said node calculator means; and means for providing a decoded signal on the basis of the nodes stored in said trace memory means corresponding to the most likely path data.

Claim 3

A Viterbi decoder in accordance with claim 1, wherein said nodes are represented by a binary code and said means for providing includes means for generating said decoded signal in accordance with a most significant bit of one of said nodes.

Claim 4

A Viterbi decoder for decoding a received signal, and having a plurality of modes, each corresponding to a state of said decoder, comprising: branch metric calculator means for calculating branch metrics of each of the nodes on the basis of the received signal; path metric calculator means for calculating path metrics on the basis of said branch metrics; path selecting means for selecting a surviving path metric for each of the nodes on the basis of said path metrics and for providing path selecting signals indicating the surviving paths; path memory means for storing said path selecting signals generated by said path selecting means for each of the nodes; node calculator means for determining a node of a most likely path having a path history length based on one of said path selecting signals and a previously determined node; trace memory means for storing said nodes, corresponding to the most likely path data, generated by said node calculator means for the path history length; and coincidence comparator means for comparing a node determined by said node calculator means with a node stored in said trace memory means and for detecting coincidence therebetween; means for inhibiting operation of said node calculator means in response to detection of coincidence by said coincidence comparator means to start the tracing of the new most likely path and for storing a node calculated by said node calculator means in said trace memory means; and means for providing a decoded signal on the basis of the nodes stored in said trace memory means.

Claim 5

A Viterbi decoder for decoding a received signal, and having a plurality of modes, each corresponding to a state of said decoder, comprising: branch metric calculator means for calculating branch metrics of each of the nodes on the basis of the received signal; path metric calculator means for calculating path metrics on the basis of said branch metrics; path selecting means for selecting a surviving path metric for each of the nodes on the basis of said path metrics and for providing path selecting signals indicating the surviving paths; path memory means for storing said path selecting signals generated by said path selecting means for each of the nodes; node calculator means for determining a node of a most likely path having a path history length based on one of said path selecting signals and a previously determined node; trace memory means for storing said nodes, corresponding to the most likely path data, generated by said node calculator means for the path history length; and coincidence comparator means for comparing a node determined by said node calculator means with a node stored in said trace memory means and for detecting coincidence therebetween; means for inhibiting operation of said node calculator means in response to detection of coincidence by said coincidence comparator means to start the tracing of the new most likely path and for storing a node calculated by said node calculator means in said trace memory means; and means for providing a decoded signal on the basis of the nodes stored in said trace memory means.

Claim 6

A Viterbi decoder having decoding cycles for decoding a received signal, and having a plurality of modes, each corresponding to a state of said decoder, comprising: branch metric calculator means for calculating branch metrics for each of the nodes on the basis of the received signal; path metric calculator means for calculating path metrics on the basis of said branch metrics; a path selecting means for selecting a surviving path metric for each of the nodes on the basis of said path metrics and for providing path selecting signals indicating the surviving paths; path memory means for storing said path selecting signals generated by said path selecting means for each of the nodes; node calculator means for determining a node of a most likely path having a path history length based on one of said path selecting signals and a previously determined node; trace memory means for storing said nodes, corresponding to the most likely path data, generated by said node calculator means for the path history length; coincidence comparator means for comparing a node determined by said node calculator means with a node stored in said trace memory means and for detecting coincidence therebetween; means for providing a decoded signal on the basis of nodes, corresponding to the most likely path, stored in said trace memory means; storing means for storing a given node in said trace memory means, when no coincidence is detected within one of the decoding cycles; and means for halting said decoding when coincidence is detected by said coincidence comparator means within one of the decoding cycles, and for continuing said decoding in another decoding cycle when coincidence is not detected.

Claim 7

A Viterbi decoder having decoding cycles for decoding a received signal, and having a plurality of modes, each corresponding to a state of said decoder, comprising: branch metric calculator means for calculating branch metrics for each of the nodes on the basis of the received signal; path metric calculator means for calculating path metrics on the basis of said branch metrics; a path selecting means for selecting a surviving path metric for each of the nodes on the basis of said path metrics and for providing path selecting signals indicating the surviving paths; path memory means for storing said path selecting signals generated by said path selecting means for each of the nodes; node calculator means for determining a node of a most likely path having a path history length based on one of said path selecting signals and a previously determined node; trace memory means for storing said nodes, corresponding to the most likely path data, generated by said node calculator means for the path history length; coincidence comparator means for comparing a node determined by said node calculator means with a node stored in said trace memory means and for detecting coincidence therebetween; means for providing a decoded signal on the basis of nodes, corresponding to the most likely path, stored in said trace memory means; storing means for storing a given node in said trace memory means, when no coincidence is detected within one of the decoding cycles; and means for halting said decoding when coincidence is detected by said coincidence comparator means within one of the decoding cycles, and for continuing said decoding in another decoding cycle when coincidence is not detected.

Claim 8

A Viterbi decoder in accordance with claim 4, wherein: the decoding cycles each comprise an input-output stage and a plurality of trace states, wherein said means for providing a decoded signal includes reading means for reading node data from said trace memory means during the input-output state, wherein said means for storing a given node includes a means for storing the given node during the input-output state, and wherein said trace memory means includes means for storing the node data calculated by the node calculator means in each of the trace states.

Claim 9

A Viterbi decoder in accordance with claim 5, wherein said coincidence comparator means carries out said comparison for detecting coincidence in each of the trace states in a decoding cycle.

Claim 10

A Viterbi decoder in accordance with claim 5, wherein said coincidence comparator means carries out said comparison for detecting coincidence only in the last trace state in a decoding cycle.

Claim 11

A Viterbi decoder in accordance with claim 7, wherein said reading means includes means for reading node data from said trace memory means during the last trace state of a decoding cycle.

Claim 12

A Viterbi decoder in accordance with claim 7, wherein said reading means includes means for reading node data from said trace memory means during the first trace state sate of a decoding cycle.

Claim 13

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

Claim 14

A Viterbi decoder in accordance with claim 10, wherein said storing means includes means for storing a minimum path metric node when said decoding is continued in another decoding cycle and for using the thus stored minimum path metric node as a starting node of the most likely path after the coincidence is detected.

Claim 15

A Viterbi decoder in accordance with claim 10, wherein said storing means includes means for storing a minimum path metric code number as said given node stored in said trace memory in a continued decoding cycle, and for using the thus stored minimum path metric node as a starting node of the most likely path after the coincidence is detected.

Claim 16

A Viterbi decoder in accordance with claim 10, wherein said storing means includes means for storing a dummy node as said given node stored in said trace memory in a continued decoding cycle, and for using the thus stored dummy node as a starting node on the most likely path after the coincidence is detected.

Claim 17

A Viterbi decoder in accordance with claim 10, wherein said storing means includes means for storing a dummy node as said given node stored in said trace memory means in a continued decoding cycle, and wherein said coincidence comparator means includes means for inhibiting said comparing in a continued decoding cycle, and said storing means includes means for storing, when said coincidence is inhibited, the node calculated by said node calculator means in said trace memory means.

Claim 18

A Viterbi decoder having decoding cycles for decoding a received signal, and having a plurality of nodes, each corresponding to a state of said decoder, comprising: branch metric calculator means for calculating branch metrics for each of the nodes on the basis of the received signal; path metric calculator means for calculating path metrics on the basis of said branch metrics; path selecting means for selecting a surviving path metric for each of the nodes on the basis of said path metrics and for providing path selecting signals indicating the surviving paths; path memory means for storing said path selecting signals generated by said path selecting means for each of the nodes; node calculator means for determining a node of a most likely path based on one of said path selecting signals and a previously determined node; trace memory means for storing said nodes, corresponding to the most likely path data, generated by said node calculator means; and means for providing a decoded signal on the basis of the nodes stored in said trace memory means, and for storing a given node in said trace memory means in each of said decoding cycles.

Claim 19

A Viterbi decoder having decoding cycles for decoding a received signal, and having a plurality of nodes, each corresponding to a state of said decoder, comprising: branch metric calculator means for calculating branch metrics for each of the nodes on the basis of the received signal; path metric calculator means for calculating path metrics on the basis of said branch metrics; path selecting means for selecting a surviving path metric for each of the nodes on the basis of said path metrics and for providing path selecting signals indicating the surviving paths; path memory means for storing said path selecting signals generated by said path selecting means for each of the nodes; node calculator means for determining a node of a most likely path based on one of said path selecting signals and a previously determined node; trace memory means for storing said nodes, corresponding to the most likely path data, generated by said node calculator means; and means for providing a decoded signal on the basis of the nodes stored in said trace memory means, and for storing a given node in said trace memory means in each of said decoding cycles.

Claim 20

A Viterbi decoder in accordance with claim 13, further comprising: minimum path metric node determining means for determining a minimum path metric node on the basis of said path metrics of each node calculated by the path selecting means; detecting means for detecting completion of decoding of the received signal; and trace control means for restarting decoding of the received signal from a trace starting node which is set to the minimum path metric code determined by the minimum path metric node determining means when when completion of a previous decoding of the received signal is detected by the detecting means.

Claim 21

A Viterbi decoder in accordance with claim 16, wherein said trace control means includes means for addressing said trace memory means so as to circulate through addresses in both increment and decrement directions of the trace memory means, and for storing the most likely path and said given node in said trace memory means in opposite directions; address coincidence detecting means for detecting coincidence of the address in both addressing directions and for inhibiting operation of said node calculator means when coincidence is detected by said address coincidence detecting means.

Claim 22

A Viterbi decoder in accordance with claim 15, wherein said trace control means includes means for addressing said trace memory means so as to circulate through addresses in both increment and decrement directions of the trace memory means, and for storing the most likely path and said given node in said trace memory means in opposite directions and non-correlatively.

Claim 23

A Viterbi decoder in accordance with claim 14, wherein said trace memory means has a length corresponding to a number of decoding cycles until coincidence is detected.