Convolutional decoder

Claim 2

A decoder for correcting and decoding convolutional data which coalesces into a predetermined plurality of possible states, said data being in branch intervals corresponding to decoded message digits, comprising correlation means having an input to which received convolutional data is applied for computing a correlation between said received data and each of a plurality of possible transmitted sequences of data, trellis data generator communicating with said correlation means for selecting from among said possible transmitted sequences a plurality of survivor sequences having relatively large correlations and establishing data indicating paths of said selected survivor sequences as sequences of transitions between states, comparator means communicating with said correlation means for mutually comparing those of said correlations that correspond to said survivor sequences to select a sole survivor sequence having the greatest correlation, and trace means connected to said trellis data generator means and to said comparator meanS for transforming by code-characteristic rules at least one branch of at least one of said transition sequences into a decoded message digit.

Claim 3

A decoder as defined in claim 1 wherein said trace means comprises means for changing by code-characteristic rules at least one of the branches of at least one of said transition sequences into state information, and means for interpreting by code-characteristic rules at least one of the branches of state information of at least said sole survivor sequence into at least one decoded message digit.

Claim 4

A decoder as defined in claim 2 wherein said means for changing comprises means for changing at least one of the branches of a plurality of said transition sequences into state information, and said comparator means comprises means for identifying the state information corresponding to said sole survivor sequence.

Claim 5

A decoder as defined in claim 3 wherein said means for interpreting comprises means for interpreting at least one of the branches of state information of only said sole survivor sequence.

Claim 6

A decoder as defined in claim 2 wherein said means for changing comprises means for changing at least one of the branches of only the transition sequence representing said sole survivor sequence, and said means for interpreting comprises means for interpreting at least one of the branches of said sole survivor sequence into decoded message digits.

Claim 7

A decoder as defined in claim 1 wherein said trace means comprises means for transforming one branch of at least one of said transition sequences into a decoded message digit.

Claim 8

A decoder as defined in claim 1 wherein at least one of said convolutional code, survivor sequences, and decoded message, is in binary code form.

Claim 9

A decoder as defined in claim 1 wherein said trellis data generator means comprises means for selecting from among said possibly transmitted sequences, upon consideration of each received branch, a pluraliy of survivor sequences including one survivor sequence terminating in each state at the newer-data end of each sequence, and wherein said one survivor sequence terminating in eAch state is one whose correlation is at least as great as the correlation of every other possibly tr8nsmitted sequence terminating in the same state.

Claim 10

A decoder as defined in claim 1 wherein said trellis data generator means comprises means for expressing said survivor sequences in a data form which, as to the sequence of states previously occupied by a data sequence, has a different predetermined meaning for a data sequence currently in one state than for a data sequence currently in another state.

Claim 11

A decoder as defined in claim 1 wherein said correlation means comprises means for accumulating a sum of incremental correlations of successive branches, said sum indicating the liklihood that a corresponding one of said possibly transmitted sequences is the sequence that was transmitted.

Claim 12

A decoder as defined in claim 10 wherein said means fOr accummulating a sum comprises means for maintaining a rescaled cumulative sum, said means for maintaining comprising means for adding a new incremental correlation and deducting a predetermined number upon each branch interval to prevent accumulating register overflow.

Claim 13

A decoder as defined in claim 1 wherein said correlation means comprises storage means for storing previous correlations corresponding to previous possibly transmitted sequences of data branches, means for generating correlation modifying data indicating the incremental correlation for a new branch of received data correlated with each of a plurality of possibly transmitted data for the new branch interval, and means for modifying the stored previous correlations in accordance with said modifying data to include therein the effects of the new data branch, upon appending a new message branch to each previous possibly transmitted sequence.

Claim 14

A decoder as defined in claim 12 wherein said means for modifying the stored correlation comprises means for maintaining a rescaled cumulative correlation by deducting from the cumulative correlation a predetermined number when overflow of the correlation accumulating registers is imminent.

Claim 15

A decoder as defined in claim 12 wherein said means for modifying comprises a plurality of combining elements for combining said previous correlation, upon consideration of an appended data branch, with a plurality of modifying data corresponding to a like plurality of said possible transmitted sequences to produce a like plurality of new correlations corresponding respectively to said possibly transmitted sequences, said combining elements communicating with said trellis data generator to transmit said new correlations thereto for comparison, and said storage means communicating with said trellis data generator to subsequently receive survivor correlation selection information therefrom.

Claim 16

A decoder as defined in claim 12 wherein said means for modifying comprises a plurality of combining elements for combining each of a plurality of previous correlations, upon consideration of an appended data branch, with a plurality of modifying data corresponding to a like plurality of possibly transmitted sequences to produce a like plurality of new correlations corresponding to said possibly transmitted sequences, and wherein said means for modifying further comprises multiplex means for selectively gating into said storage means from said combining elements a new correlation to replace each of said previous correlations, said storage means communicating with said trellis data generator means to transmit the correlation contents of said storage meanS thereto for comparison, and said multiplex means communicating with said trellis data generator means to subsequently receive therefrom survivor selection information for said selective gating by said multiplex means.

Claim 17

A decoder as defined in claim 12 wherein said storage means comprises a plurality of register means for storing which are serially accessible for writing and reading correlation data; and said means for modifying comPrises a plurality of serially oPerable combiners each for combining said modifying data in serial fashion with a particular one of a plurality of said previous correlations to produce modified correlation data, selection logic means communicating w6th said storage means and with said combiners and with said trellis data generator means for selecting said particular one in accordance with commands received from the trellis data generator means, said commands being said sequences of transmitions between states evaluated in an immediately preceding branch interval, and means for reloading said storage means with said modified correlation data comprising connection means connecting each of said combiners with one of said register means.

Claim 18

A decoder as defined in claim 1 wherein said trace means comprises data register means for storing said sequence of transitions between states, a switchable analog circuit simulating said plurality of survivor sequences as a plurality of signal transmission paths through said states, said analog circuit simulation being switchably established in accordance with said sequences of transitions between states in said data register means, said states being represented topologically by circuit nodes, and wherein said trace means also comprises a signal means propagated through said analog circuit in a trace-back direction, and responsive to said comparator means for tracing said sole survivor sequence into states, and wherein said trace means further comprises logic circuit means for interpreting by code-characteristic logic rules at least one of said states of said sole survivor sequence into decoded message digits.

Claim 19

Decoding apparatus as defined in claim 17 wherein said analog circuit comprises a plurality of relays, each relay corresponding to a state and also to a branch interval and having a plurality of switching positions, each switching position corresponding to a signal path, each of said relays being responsive to select a swtiching position in accordance with contents of said data register means to simulate said survivor paths.

Claim 20

Decoding apparatus as defined in claim 17 wherein said analog circuit comprises static logic gate circuit means, said signal transmission paths comprise digital circuit paths, and said signal means comprises means communicating with said gate circuit means and with said comparator means for producing digital signals selectably connectible to a survivor path of said gate circuit means in dependence upon the selection made by said comparator means.

Claim 21

A decoder as defined in claim 1 wherein said trace means comprises a plurality of trace register means each representing a state and each preloaded with data identifying at least one possibly transmitted sequence at and near the decoding depth, interchange means interconnecting said trace register means to selectively interchange their data among said trace register means in a sequence in accordance with said sequences of transitions, in a trace-forward direction, to identify the possibly transmitted sequence finally occupying each of the states at the newer-data end of said survivor sequences, and wherein said trace means further comprises logic means for interpreting into a decoded message digit at least one of the digits of the preloading data corresponding to at least said sole survivor sequence.

Claim 22

A decoder as defined in claim 20 wherein said trace means further comprises preload logic means communicating with said trace register means and with said trellis data generator means for manipulating a plurality of the earlier-received branch intervals of said sequences of transmissions in accordance with code-characteristic rules to determine a plurality of initial segments of trial decoded messages at and near the decoding depth, and wherein said initial segments serve as said identifying data with which said plurality of trace register means are preloaded, and wherein said logic means comprises selective accessing means responsive to said comparator means.

Claim 23

A decoder as defined in claim 1 wherein said trace means comprises a plurality of trellis register means, each corresponding to a state, for storing said transition sequences, sequential access circuits for reading said transition sequences from said trellis register means, a plurality of M-digit registers, each corresponding to a state and each presettable with data, translation logic means for translating in accordance with code-characteristic rules the oldest M branch intervals of a plurality of transition sequences into M-digit initial segments of trial decoded messages, one segment being for each of said M-digit registers, preset means for presetting each of said M-digit registers with a different one of said M-digit initial segments of trial decoded-message data, interchange circuit means interconnecting said M-digit registers to selectively interchange their data among said registers in a time sequence in accordance with said transition sequence data in a trace-forward direction, to ascertain for a survivor sequence corresponding to each of said initial message segments the state which the path occupies at the new-data end of the survivor sequence and output means for reading after the interchanging operation the contents of one of said M-digit registers.

Claim 24

A decoder as defined in claim 22 wherein said output means comprises means for selectively reading after the interchanging operation the contents of a selected one of said M-digit registers, the register selected being that whose state is specified by said comparator means as the new state of said sole survivor sequence.

Claim 25

A decoder as defined in claim 22 wherein each of said trellis register means comprises recirculable register means having L times M stages, and wherein said interchange circuit means comprises means for recirculating said initial segments L times through said M-digit registers simultaneously with selectively interchanging said segments.

Claim 26

A decoder as defined in claim 1 wherein said trace means comprises a plurality of M-branch register means for storing M-branch portion of said sequences of transitions, said M-branch register means being sequentially accessible, message compute means comprising translation logic means for translating in accordance with code-characteristic rules said M-branch portions from said M-branch register means into a plurality of M-digit initial segments of trial decoded messages, said translation logic means comprising a plurality of trial message register means for storing said M-branch segments of trial decoded messages, L-branch register means for storing L-branch portions of said transition sequence data received immediately after said M-branch portions, said L-branch register means being sequentially accessible, a plurality of trace register means responsive to said L-branch portions of data from said L-branch register means, for tracing forward through said L-branch portions to ascertain a state of origin of the L-branch portion of each survivor sequence, and logic circuit means connected to receive sole survivor path selection information from said comparator means and to receive state of origin information from said trace register means and responsive thereto for identifying and accessing a particular trial message register means containing a segment of said sole survivor path.

Claim 27

A decoder as defined in claim 1 wherein said trace means comprises a plurality of trace register means each corresponding to a state which are presettable with data, preset circuit means communicating with said comparator means and with said trace register means for presetting indentifying indicia into said trace register means to distinguish at least a trace register means corresponding to said sole survivor sequence from the others, a plurality of trellis register means each corresponding to a state for storing said transition sequences, sequential access circuits for reading said transition sequences from said trellis registeR means with the newer branch intervals being read first, interchange circuit means interconnecting said trace register means for data interchange to selectively relocate the identifying indicia in the trace registers in accordance with transition sequences from said sequential access cicuits in a trace-back direction, to identify the states at and near decoding depth of said sole survivor sequence, and logic circuit means receiving at its input terminals after partial completion of the data interchange operation and thereafter during the interchange operation said identifying indicia from said trace registers disclosing the oldest states of said sole survivor sequence, for converting the oldest-states information by code-characteristic logic rules into one or more decoded message digits in original order to be output at the output terminals of said logic circuit means.

Claim 28

Decoding apparatus as defined in claim 26 wherein said trellis register means comprises shift registers and said sequential accessing circuits comprise shifting means for shifting said shift registers and connecting circuits for connecting the output of one stage of each trellis register means to said interchange circuit means.

Claim 29

Decoding apparatus as defined in claim 26 wherein said logic circuit means comprises a first multiple-stage shift register connected to receive decoded message digits serially during the trace-back operation with the oldest bit being the least received, a second multiple-stage shift register connected to said first multiple-stage shift register to receive the decoded message digits by parallel data transfer from said first multiple-stage shift register after the trace-back interchange operation, and timing circuits controlling the system and to shift the second multiple-stage shift register after it receives said digits to put out decoded message digits sequentially with the oldest message digit first.