Shift-correcting code system with efficient symbol-to-channel bit transformation

Claim 2

A parity symbol-to-modulation codeword encoder which generates, from parity symbols in a finite field, codewords of a modulation code, said codewords comprising runs of bits of a first bit value of minimum length d and maximum length k, said encoder comprising: means for receiving a current set of input bits corresponding to a current one of said finite field parity symbols; means for appending to said set of input bits a set of b appendage bits so as to form a codeword of said modulation code, said means for appending being in a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value when said current state does not correspond to said first state value, wherein said binary symbol is a bit of said first value when said current parity symbol is said first one of said set of parity symbols, and said binary symbol is a bit of a second bit value otherwise, each bit of said first bit value being a zero bit and each bit of said second bit value being a one bit, each codeword of said channel modulation code comprising a run of zero bits, successive ones of said codewords being separated by a one bit; and means for setting the state of said appending means for a next set of input bits to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise.

Claim 3

The encoder of claim 1 wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set of 01 and 10, and wherein said first one of said set of parity symbols is 10 and wherein said set of state values comprises two state values.

Claim 4

The encoder of claim 1 wherein b satisfies the relationship: d=b, and k=2b+3.

Claim 5

A parity symbol-to-modulation codeword encoder which generates, from parity symbols in a finite field, codewords of a modulation code, said codewords comprising runs of bits of a first bit value of minimum length d and maximum length k, said encoder comprising: means for receiving a current set of input bits corresponding to a current one of said finite field parity symbols; means for appending to said set of input bits a set of b appendage bits so as to form a codeword of said modulation code, said means for appending being in a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value when said current state does not correspond to said first state value, and means for setting the state of said appending means for a next set of input bits to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise, wherein said binary symbol is a bit of a second bit value, wherein said appendage bits comprise the most significant bits of said channel word, said binary symbol of said appendage bits being the most significant bit thereof and said set of input bits being the least significant bits thereof, wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 6

A parity symbol-to-modulation codeword encoder which generates, from parity symbols in a finite field, codewords of a modulation code, said codewords comprising runs of bits of a first bit value of minimum length d and maximum length k, said encoder comprising: means for receiving a current set of input bits corresponding to a current one of said finite field parity symbols; means for appending to said set of input bits a set of b appendage bits so as to form a codeword of said modulation code, said means for appending being in a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value when said current state does not correspond to said first state value, and means for setting the state of said appending means for a next set of input bits to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise, wherein said binary symbol is a bit of a second bit value, wherein said appendage bits comprise the most significant bits of said channel word, said binary symbol of said appendage bits being the most significant bit thereof and said set of input bits being the least significant bits thereof, wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 7

The encoder of claim 4 wherein b satisfies the following relationship: d=b-1, and k=b+3.

Claim 8

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity symbols in said finite field is computed, wherein said block of parity symbols is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, an encoder for transforming said block of parity symbols in said finite field to said check block of (d,k)-constrained symbols, said encoder comprising: means for receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; means for appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol, said means for appending being in a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of said first bit value when said current parity symbol is first one of said set of parity symbols, and said binary symbol equals a bit of a second bit value otherwise, wherein each bit of said first bit value is a zero bit and each bit of said second bit value is a one bit, and wherein each (d,k)-constrained symbol comprises a run of zero bits of minimum run length d and maximum run length k, successive ones of said (d,k)-constrained symbols being separated by a one bit; and means for setting the state of said appending means for a next set of input bits to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to the other one of said two state values otherwise.

Claim 9

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity symbols in said finite field is computed, wherein said block of parity symbols is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, an encoder for transforming said block of parity symbols in said finite field to said check block of (d,k)-constrained symbols, said encoder comprising: means for receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; means for appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol, said means for appending being in a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of said first bit value when said current parity symbol is first one of said set of parity symbols, and said binary symbol equals a bit of a second bit value otherwise, wherein each bit of said first bit value is a zero bit and each bit of said second bit value is a one bit, and wherein each (d,k)-constrained symbol comprises a run of zero bits of minimum run length d and maximum run length k, successive ones of said (d,k)-constrained symbols being separated by a one bit; and means for setting the state of said appending means for a next set of input bits to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to the other one of said two state values otherwise.

Claim 10

The encoder of claim 6 wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10, and wherein said first one of said set of parity symbols is 10 and wherein said set of state values comprises two state values.

Claim 11

The encoder of claim 6 wherein b satisfies the following relationship: d=b, and k=2b=3.

Claim 12

The encoder of claim 6 wherein said means for setting said state comprises: means responsive whenever said current set of input bits corresponds to a leading (d,k)-constrained symbol of one of said check blocks immediately following the last (d,k)-constrained symbol of a previous one of said message blocks in said channel for initializing the value of said state to a first one of said set of state values if the run length of said last symbol of said previous message block is less than d and for initializing said state to another one of said set of state values otherwise.

Claim 13

The encoder of claim 6 wherein said means for appending comprise means for generating the most significant bit to be appended to said two-bit word, said means for generating said most significant bit comprising: an AND gate having two logic inputs, one of said logic inputs of said AND gate being controlled by the logical inverse of said state value and the other of said logic inputs of said AND gate being controlled by the most significant bit of said current set of input bits.

Claim 14

The encoder of claim 6 wherein said system further comprises a decoder which back-transforms said (d,k)-constrained symbols formed by said means for appending into said set of input bits, said decoder comprising: means for stripping the bits appended by said means for appending from said set of input bits and for transmitting said set of input bits.

Claim 15

The encoder of claim 6 wherein said means for appending comprises: means responsive whenever said current set of input bits corresponds to a last (d,k)-constrained symbol of one of said check blocks immediately preceding the first (d,k)-constrained symbol of a next one of said message blocks in said channel for inserting a linking (d,k)-constrained symbol between said check block and said message block corresponding to a third, fourth or fifth one of said set of parity symbols whenever the run length of said first (d,k)-constrained symbol of said next message block is less than, equal to or greater than d-1, respectively.

Claim 16

The encoder of claim 12 wherein said third, fourth and fifth ones of said set of parity symbols are 01, 10 and 00, respectively.

Claim 17

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity symbols in said finite field is computed, wherein said block of parity symbols is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, an encoder for transforming said block of parity symbols in said finite field to said check block of (d,k)-constrained symbols, said encoder comprising: means for receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; means for appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol, said means for appending being in a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, and means for setting the state of said appending means for a next set of input bits to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to the other one of said two state values otherwise, wherein said binary symbol being a bit of a second bit value, said binary symbol is a bit of a said first bit value when said current parity symbol is first one of said set of parity symbols, said binary symbol equaling a bit of a second bit value otherwise, wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 18

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity symbols in said finite field is computed, wherein said block of parity symbols is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, an encoder for transforming said block of parity symbols in said finite field to said check block of (d,k)-constrained symbols, said encoder comprising: means for receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; means for appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol, said means for appending being in a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, and means for setting the state of said appending means for a next set of input bits to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to the other one of said two state values otherwise, wherein said binary symbol being a bit of a second bit value, said binary symbol is a bit of a said first bit value when said current parity symbol is first one of said set of parity symbols, said binary symbol equaling a bit of a second bit value otherwise, wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 19

The encoder of claim 14 wherein b satisfies the following relationship: d=b-1, and k=b+3.

Claim 20

A parity symbol-to-modulation codeword encoding method for generating, from parity symbols in a finite field, codewords of a modulation code, said codewords comprising runs of bits of a first bit value of minimum length d and maximum length k, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said finite field parity symbols; appending to said set of input bits a set of b appendage bits so as to form a codeword of said modulation code in accordance with a state, said appendage bits comprising one of: (a) b bits of said first bit value when said state corresponds to a first one of a set of state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of said first bit value when said current parity symbol is first one of said set of parity symbols, and said binary symbol is a bit of a second bit value otherwise, wherein each bit of said first bit value is a zero bit and each bit of said second bit value is a one bit, and wherein each codeword of said channel modification code comprises a run of zero bits, successive ones of said codewords being separated by a one bit; and setting said state to one of: (a) a predetermined one of said state values if said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise.

Claim 21

A parity symbol-to-modulation codeword encoding method for generating, from parity symbols in a finite field, codewords of a modulation code, said codewords comprising runs of bits of a first bit value of minimum length d and maximum length k, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said finite field parity symbols; appending to said set of input bits a set of b appendage bits so as to form a codeword of said modulation code in accordance with a state, said appendage bits comprising one of: (a) b bits of said first bit value when said state corresponds to a first one of a set of state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of said first bit value when said current parity symbol is first one of said set of parity symbols, and said binary symbol is a bit of a second bit value otherwise, wherein each bit of said first bit value is a zero bit and each bit of said second bit value is a one bit, and wherein each codeword of said channel modification code comprises a run of zero bits, successive ones of said codewords being separated by a one bit; and setting said state to one of: (a) a predetermined one of said state values if said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise.

Claim 22

The method of claim 16 wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10 and wherein said first one of said set of parity symbols is 10 and wherein said set of state values comprises two state values.

Claim 23

The method of claim 16 wherein be satisfies the following relationship: d=b, k=2b+3.

Claim 24

A parity symbol-to-modulation codeword encoding method for generating, from parity symbols in a finite field, codewords of a modulation code, said codewords comprising runs of bits of a first bit value of minimum length d and maximum length k, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said finite field parity symbols; appending to said set of input bits a set of b appendage bits so as to form a codeword of said modulation code in accordance with a state, said appendage bits comprising one of: (a) b bits of said first bit value when said state corresponds to a first one of a set of state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise; and setting said state to one of: (a) a predetermined one of said state values if said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise, wherein said binary symbol is a bit of a second bit value, said appendage bits comprise the most significant bits of said channel word, said binary symbol of said appendage bits being the most significant bit thereof and said set of input bits being the least significant bits thereof, wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 25

A parity symbol-to-modulation codeword encoding method for generating, from parity symbols in a finite field, codewords of a modulation code, said codewords comprising runs of bits of a first bit value of minimum length d and maximum length k, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said finite field parity symbols; appending to said set of input bits a set of b appendage bits so as to form a codeword of said modulation code in accordance with a state, said appendage bits comprising one of: (a) b bits of said first bit value when said state corresponds to a first one of a set of state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise; and setting said state to one of: (a) a predetermined one of said state values if said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise, wherein said binary symbol is a bit of a second bit value, said appendage bits comprise the most significant bits of said channel word, said binary symbol of said appendage bits being the most significant bit thereof and said set of input bits being the least significant bits thereof, wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 26

The method of claim 19 wherein b satisfies the following relationship: d=b-1, and k=b+3.

Claim 27

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity elements in said finite field is computed, wherein said block of parity elements is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, a method for transforming said block of parity elements in said finite field to said check block of (d,k)-constrained symbols, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol in accordance with a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of said first bit value when said current parity symbol is a first one of said set of parity symbols, said binary symbol equalling a bit of a second value otherwise, wherein each bit of said first bit value is a zero bit and each bit of said second bit value is a one bit, and wherein each (d,k)-constrained symbol comprises a run of zero bits of minimum run length d and maximum run length k, successive ones of said (d,k)-constrained symbols being separated by a one bit; and setting said state to one of: (a) a predetermined one of said state value if said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise.

Claim 28

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity elements in said finite field is computed, wherein said block of parity elements is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, a method for transforming said block of parity elements in said finite field to said check block of (d,k)-constrained symbols, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol in accordance with a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value when said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of said first bit value when said current parity symbol is a first one of said set of parity symbols, said binary symbol equalling a bit of a second value otherwise, wherein each bit of said first bit value is a zero bit and each bit of said second bit value is a one bit, and wherein each (d,k)-constrained symbol comprises a run of zero bits of minimum run length d and maximum run length k, successive ones of said (d,k)-constrained symbols being separated by a one bit; and setting said state to one of: (a) a predetermined one of said state value if said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise.

Claim 29

The method of claim 21 wherein said predetermined one of said set of parity symbols in said finite field is 00 and the remaining parity symbols of said set are 01 and 10, and wherein said first one of said set of parity symbols is 10 and wherein said set of state values comprises two state values.

Claim 30

The method of claim 21 wherein b satisfies the following relationship: d=b, and k=2b+3.

Claim 31

The method of claim 21 wherein the step of setting said state comprises: whenever said current set of input bits is to be transformed to a leading (d,k)-constrained symbol of one of said check blocks immediately following a last (d,k)-constrained symbol of a previous one of said message blocks in said channel, initializing the value of said state to a first one of said set of state values if the run length of said last symbol of said previous message block is less than d and initializing said state to an other one of said set of state values otherwise.

Claim 32

The method of claim 21 further comprising: whenever said current set of input bits is to be transformed to a last (d,k)-constrained symbol of one of said check blocks immediately preceding the first (d,k)-constrained symbol of a next one of said message blocks in said channel, inserting a linking (d,k)-constrained symbol between said check block and said message block corresponding to a third, fourth or fifth one of said set of parity symbols whenever the run length of said first (d,k)-constrained symbol of said next message block is less than, equal to or greater than d-1, respectively.

Claim 33

The method of claim 25 wherein said third, fourth and fifth ones of said set of parity symbols are 01, 10 and 00, respectively.

Claim 34

The method of claim 21 wherein each input set of bits is followed by a successive input set of bits, said method further comprising repeating the sensing, receiving, generating, appending and setting steps for each successive input set of bits; wherein said generating step is carried out with a first value of b for initial ones of said sets of input bits and a second value of b for the remaining sets of input bits.

Claim 35

The method of claim 27 wherein: said first value of b satisfies d=b-1 and k=b+3; and said second value of b satisfies d=b and k=2b+3.

Claim 36

The method of claim 28 wherein said initial symbols are one of: (a) the leading symbol of said check block or (b) the first and second leading symbols of said check block.

Claim 37

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity elements in said finite field is computed, wherein said block of parity elements is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, a method for transforming said block of parity elements in said finite field to said check block of (d,k)-constrained symbols, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol in accordance with a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value if said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of a second value; and setting said state to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise, wherein said appendage bits comprise the most significant bits of said (d,k)-constrained symbol formed by the appending step, said binary symbol of said appendage bits being the most significant bit thereof and said set of input bits being the least significant bits thereof, wherein said predetermined one of said set of parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 38

In an error correction modulation code system in which a message block of (d,k)-constrained symbols is converted to a block of elements in a finite field from which a block of parity elements in said finite field is computed, wherein said block of parity elements is transformed to a check block of (d,k)-constrained symbols for transmission with said message block through a channel as part of an alternating succession of message blocks and check blocks therein, a method for transforming said block of parity elements in said finite field to said check block of (d,k)-constrained symbols, said method comprising the steps of: receiving a current set of input bits corresponding to a current one of said parity symbols of said finite field; appending to said set of input bits a set of b appendage bits so as to form a (d,k)-constrained symbol in accordance with a current state corresponding to one of a set of state values, said appendage bits comprising one of: (a) b bits of said first bit value if said current state corresponds to a first one of said state values, and (b) a binary symbol and b-1 bits of said first bit value otherwise, wherein said binary symbol is a bit of a second value; and setting said state to one of: (a) a predetermined one of said state values when said current one of said parity symbols is a predetermined one of a set of parity symbols in said finite field, and (b) to an other one of said state values otherwise, wherein said appendage bits comprise the most significant bits of said (d,k)-constrained symbol formed by the appending step, said binary symbol of said appendage bits being the most significant bit thereof and said set of input bits being the least significant bits thereof, wherein said predetermined one of said set of parity symbols of said set are 01 and 10 and wherein said set of state values comprises two state values.

Claim 39

The method of claim 30 wherein b satisfies the following relationship: d=b-1, and k=b+3.