Method and apparatus for implementing a maximum-likelihood decoder in a hypercube network

Claim 3

A method according to claim 1, and wherein said deiving/interchanging step is further characterized by: communicating only between adjacent neighboring processors in said n-cube configuration wherein each processor represents different states of the decoder at different stages on said equivalent trellis, according to the relation: x=ρ.sup.(k) (x), meaning that processor x in a binary notation represent state x at stage k, where ρ.sup.(k) (x) is the cyclic right shift of x by k binary positions.

Claim 4

A method according to claim 1 comprising the additional preliminary steps prior to said deriving/interchanging step of: designating one processor of the n-cube network as an origin/output processor; and broadcasting said received signals from said origin processor to all of the remaining n-cube connected processors.

Claim 5

A maximum likelihood decoding system for determining accumulated metrics and selecting survivor paths during a repetitive set of stages of a trellis code having a finite number of states M, (where M is a whole integer), said system comprising: N processors (N=2 n ) placed at the vertices of an n-dimensional cube, where n is a whole integer, with each processor assigned to represent more than one state at different stages, k, in a repeating set of stages in the trellis code --that is--each processor x is assigned state x according to the relation: x=ρ.sup.(k) (x), meaning that processor x represents state x at stage k, where ρ.sup.(k) (x) is the cyclic right shift of x by k binary position and k is number of the stages which make up a set in the trellis; means for comprising at each processor accumulated metrics and survivors at said different states of the trellis code at correspondingly different stages numbered (k=0, k=1, k=2, etc.) on the trellis; and bidirectional processor-communication links along the edges only of said n-dimensional cube for exchanging said computed accumulated metrics and survivors only between adjacent neighboring processors.

Claim 6

A maximum likelihood decoding system for determining accumulated metrics and selecting survivor paths during a repetitive set of stages of a trellis code having a finite number of states M, (where M is a whole integer), said system comprising: N processors (N=2 n ) placed at the vertices of an n-dimensional cube, where n is a whole integer, with each processor assigned to represent more than one state at different stages, k, in a repeating set of stages in the trellis code --that is--each processor x is assigned state x according to the relation: x=ρ.sup.(k) (x), meaning that processor x represents state x at stage k, where ρ.sup.(k) (x) is the cyclic right shift of x by k binary position and k is number of the stages which make up a set in the trellis; means for comprising at each processor accumulated metrics and survivors at said different states of the trellis code at correspondingly different stages numbered (k=0, k=1, k=2, etc.) on the trellis; and bidirectional processor-communication links along the edges only of said n-dimensional cube for exchanging said computed accumulated metrics and survivors only between adjacent neighboring processors.

Claim 7

A decoding system in accordance with claim 4, wherein one processor from said plurality is designated as an input processor and further comprising: input means at said input processor for receiving a coded line sequence to be broadcast to every one of said processors; and output means at said one processor for outputting a chosen maximum-likelihood sequence as a decoded output from said decoding system.

Claim 8

A maximum-likelihood decoding method for decoding sequences generated by a convolutional encoding having M=2 m states by considering at the decoder all possible paths on an n-cube trellis and finding the most likely path according to a specified goodness criterion involving decoding parameters, said method comprising the steps of: forming a concurrent processor network of N=2 n microprocessors interconnected as an n-dimensional cube having one microprocessor each at the vertices of said cube and bidirectional communication links for said microprocessors only along the edges of said cube and corresponding to all paths to be checked on said n-cube trellis by transmitting/receiving said decoding parameters over said communication links; broadcasting a sequence to be decoded to every one of said microprocessors; assigning each of the M states on said n-cube trellis to each of the N microprocessors according to the formula: x=ρ.sup.(k) (x) wherein, when expressed in binary notations, microprocessor x represents state x at stage k and the function ρ.sup.(k) is the cyclic right shift of x by k binary positions and M, m, N and n are whole integers; computing and storing locally at each microprocessor the decoding parameters; and transmitting/receiving said decoding parameters between neighboring processors in said n-dimensional cube.

Claim 9

A maximum-likelihood decoding method for decoding sequences generated by a convolutional encoding having M=2 m states by considering at the decoder all possible paths on an n-cube trellis and finding the most likely path according to a specified goodness criterion involving decoding parameters, said method comprising the steps of: forming a concurrent processor network of N=2 n microprocessors interconnected as an n-dimensional cube having one microprocessor each at the vertices of said cube and bidirectional communication links for said microprocessors only along the edges of said cube and corresponding to all paths to be checked on said n-cube trellis by transmitting/receiving said decoding parameters over said communication links; broadcasting a sequence to be decoded to every one of said microprocessors; assigning each of the M states on said n-cube trellis to each of the N microprocessors according to the formula: x=ρ.sup.(k) (x) wherein, when expressed in binary notations, microprocessor x represents state x at stage k and the function ρ.sup.(k) is the cyclic right shift of x by k binary positions and M, m, N and n are whole integers; computing and storing locally at each microprocessor the decoding parameters; and transmitting/receiving said decoding parameters between neighboring processors in said n-dimensional cube.

Claim 10

A decoding method for determining the maximum-likelihood path of a trellis code having M=2 n states representing a line sequence generated by a convolutional encoder and subjected to channel noise, said method involving known decoding algorithms having decoding parameters to be transmitted/received between N (N=2 n ) decoding processors, with M, N and n being whole integers comprising the steps of: dividing a decoding algorithm for said processors into equal parts as a power of two from all of said states for processing of each of said equal parts by one each of a plurality of N concurrent processors; locating N=2 n processors at the vertices of an n-dimensional cube having bidirectional communication paths for said processors only along the edges of said cube; mapping a trellis with certain processors representing more than one state on the trellis in order to represent all of the M states on said trellis by said N processors, with each of said processors having direct transmitting/receiving paths from neighboring processors along the dimensions of said cube and in said trellis; and computing the maximum-likelihood path for each of the M states by each of the n microprocessors said trellis wherein said processors represent more than one state in an order according to: x=ρ.sup.(k) (x) wherein microprocessor x represents a set of states x at stages k and the function ρ.sup.(k) is the cyclic right shift of x by k binary positions.

Claim 11

A decoding method for determining the maximum-likelihood path of a trellis code having M=2 n states representing a line sequence generated by a convolutional encoder and subjected to channel noise, said method involving known decoding algorithms having decoding parameters to be transmitted/received between N (N=2 n ) decoding processors, with M, N and n being whole integers comprising the steps of: dividing a decoding algorithm for said processors into equal parts as a power of two from all of said states for processing of each of said equal parts by one each of a plurality of N concurrent processors; locating N=2 n processors at the vertices of an n-dimensional cube having bidirectional communication paths for said processors only along the edges of said cube; mapping a trellis with certain processors representing more than one state on the trellis in order to represent all of the M states on said trellis by said N processors, with each of said processors having direct transmitting/receiving paths from neighboring processors along the dimensions of said cube and in said trellis; and computing the maximum-likelihood path for each of the M states by each of the n microprocessors said trellis wherein said processors represent more than one state in an order according to: x=ρ.sup.(k) (x) wherein microprocessor x represents a set of states x at stages k and the function ρ.sup.(k) is the cyclic right shift of x by k binary positions.

Claim 12

A maximum likelihood decoding system for determining accumulated metrics and selecting survivor paths of M states of a trellis code in network of N=2 n processors with each processor placed at the vertices of an n-dimensional cube and representing a set of S=2 s states of the decoder formed from said processors; said decoder characterized in that: each processor represents different states of the trellis code at different stages on the trellis, according to the relation: x=.sup.(k) (x), meaning that processor x represents state x at state k, where .sup.(k) (x) is the cyclic right shift of x by k binary positions.

Claim 13

A maximum likelihood decoding system for determining accumulated metrics and selecting survivor paths of M states of a trellis code in network of N=2 n processors with each processor placed at the vertices of an n-dimensional cube and representing a set of S=2 s states of the decoder formed from said processors; said decoder characterized in that: each processor represents different states of the trellis code at different stages on the trellis, according to the relation: x=.sup.(k) (x), meaning that processor x represents state x at state k, where .sup.(k) (x) is the cyclic right shift of x by k binary positions.

Claim 14

A maximum-likelihood decoding system in accordance with claim 8 and further comprising: bidirectional processor-communication links along the edges only of said n-dimensional cube for exchanging accumulated metrics and survivors.

Claim 15

A decoding system in accordance with claim 9 wherein each of said processors is characterized by means at each processor for computing its local accumulated metrics and for updating the locally-accumulated metrics by adding thereto branch metrics, and said decoding system further comprises: comparing means in each processor for comparing the local accumulated metrics with those accumulated metrics received over said links from said neighboring processors.

Claim 16

A decoding system in accordance with claim 10 and further comprising: an origin processor at one vertex only of said n-dimensional cube; and means for outputting to a user a decoded signal from said origin processor.