List Viterbi algorithms for tailbiting convolutional codes

Claim 1

A method for processing a block of symbols, said symbols having been generated using a tailbiting code represented by a trellis, said method comprising the steps of a) Viterbi decoding said block by at least one execution of a Viterbi algorithm for tailbiting codes to identify at least one of a plurality of paths through the trellis, said one path including a pair of starting and terminating states, and b) executing a List Viterbi algorithm using said pair of starting and terminating states to generate a first set of best candidate paths, wherein at least one additional candidate path is generated by using another pair of starting and terminating states associated with a different path through the trellis.

Claim 2

A method for processing a block of symbols, said symbols having been generated using a tailbiting code represented by a trellis, said method comprising the steps of a) Viterbi decoding said block by at least one execution of a Viterbi algorithm for tailbiting codes to identify at least one of a plurality of paths through the trellis, said one path including a pair of starting and terminating states, and b) executing a List Viterbi algorithm using said pair of starting and terminating states to generate a first set of best candidate paths, wherein at least one additional candidate path is generated by using another pair of starting and terminating states associated with a different path through the trellis.

Claim 7

A method of decoding a block of symbols, said symbols being encoded using a tailbiting code defined in part by a trellis, said method comprising the steps of a) successively executing a List Viterbi algorithm, each execution utilizing a respective different pair of identical encoder starting and terminating states to identify a respective set of candidate best paths, and b) selecting a number of said identified candidate best paths as globally best candidate paths.

Claim 8

A method of decoding a block of symbols, said symbols being encoded using a tailbiting code defined in part by a trellis, said method comprising the steps of a) successively executing a List Viterbi algorithm, each execution utilizing a respective different pair of identical encoder starting and terminating states to identify a respective set of candidate best paths, and b) selecting a number of said identified candidate best paths as globally best candidate paths.

Claim 12

A method of processing a sequence of blocks, said blocks having been encoded using a tailbiting convolutional code and having been transmitted in a continuous mode, said method comprising a) receiving said blocks, and b) generating lists of best candidate decodings using List Viterbi decoding, each of said lists corresponding to a respective block of said sequence of blocks, at least a subset of said lists including candidate decodings associated with different pairs of starting and terminating states.

Claim 13

A method of processing a sequence of blocks, said blocks having been encoded using a tailbiting convolutional code and having been transmitted in a continuous mode, said method comprising a) receiving said blocks, and b) generating lists of best candidate decodings using List Viterbi decoding, each of said lists corresponding to a respective block of said sequence of blocks, at least a subset of said lists including candidate decodings associated with different pairs of starting and terminating states.

Claim 14

A method for processing a block of symbols, said symbols having been generated using a tailbiting code represented by a trellis, said method comprising the steps of a) Viterbi decoding said block by at least one execution of a Viterbi algorithm for tailbiting codes to identify at least one of a plurality of paths through the trellis, said one path including a starting state and a terminating state, and b) executing a List Viterbi algorithm using said starting and terminating state to generate a first set of best candidate paths, wherein in step (a) a number of said plurality of paths are identified, each of said number of paths including a respective pair of starting and terminating states, and wherein said step (b) further comprises the steps of successively executing a List Viterbi algorithm, each of said successive executions using a respective different one of said pairs of starting and terminating states and thereby generating a number of sets of best candidate paths, and ranking said best candidate paths across all said sets to produce a list of globally best candidate paths.

Claim 15

A method for processing a block of symbols, said symbols having been generated using a tailbiting code represented by a trellis, said method comprising the steps of a) Viterbi decoding said block by at least one execution of a Viterbi algorithm for tailbiting codes to identify at least one of a plurality of paths through the trellis, said one path including a starting state and a terminating state, and b) executing a List Viterbi algorithm using said starting and terminating state to generate a first set of best candidate paths, wherein in step (a) a number of said plurality of paths are identified, each of said number of paths including a respective pair of starting and terminating states, and wherein said step (b) further comprises the steps of successively executing a List Viterbi algorithm, each of said successive executions using a respective different one of said pairs of starting and terminating states and thereby generating a number of sets of best candidate paths, and ranking said best candidate paths across all said sets to produce a list of globally best candidate paths.

Claim 16

A method for processing a block of symbols, said symbols having been generated using a tailbiting code represented by a trellis, said method comprising the steps of a) Viterbi decoding said block by at least one execution of a suboptimum Viterbi decoding algorithm for tailbiting codes to identify at least one of a plurality of paths through the trellis, said one path including a starting state and a terminating state, b) executing a List Viterbi algorithm using said starting and terminating state to generate a first set of best candidate paths, c) Viterbi decoding said block by executing said suboptimum decoding algorithm to identify one of a plurality of paths through the trellis, said decoding commencing at an offset into said block, said one path identified in this step including a starting state and a terminating state, d) executing a List Viterbi algorithm using said starting and terminating states identified in step (c) to generate a second set of best candidate paths, and e) consolidating said first and second sets to produce a list of globally best candidate paths.

Claim 17

A method for processing a block of symbols, said symbols having been generated using a tailbiting code represented by a trellis, said method comprising the steps of a) Viterbi decoding said block by at least one execution of a suboptimum Viterbi decoding algorithm for tailbiting codes to identify at least one of a plurality of paths through the trellis, said one path including a starting state and a terminating state, b) executing a List Viterbi algorithm using said starting and terminating state to generate a first set of best candidate paths, c) Viterbi decoding said block by executing said suboptimum decoding algorithm to identify one of a plurality of paths through the trellis, said decoding commencing at an offset into said block, said one path identified in this step including a starting state and a terminating state, d) executing a List Viterbi algorithm using said starting and terminating states identified in step (c) to generate a second set of best candidate paths, and e) consolidating said first and second sets to produce a list of globally best candidate paths.