Lexicographical encoding and decoding of state-dependent codes
AssigneeInternational Business Machines Corporation
InventorLyle J. Frederickson
Life of this patent
Estimating the term…
Abstract
A method and apparatus for (1) reducing storage requirements by use of novel encoding/decoding lexicographically code and decode state-dependent codes, and (2) locally reordering coded subsequences to permit direct NRZ coding, which is especially desirable when using PRML sequence detection.
Claims21
A method for lexicographically coding indicia in a state-dependent code between user data and a coded sequence thereof, comprising the steps of:
- (a) providing a coding trellis having a plurality of sets of states, each state in each set having a respective threshold equal to the number of valid code subsequences from that particular state to the end of the trellis;
- (b) determining a path through the trellis corresponding to a current state;
- and
- (c) recursively using the thresholds corresponding to successive current states to provide an invertible mapping between the user data and coded sequence thereof.
A method for lexicographically encoding an n-bit input string of binary data, which is in a state-dependent code, for use on a binary storage channel to provide an output in the form of coded subsequences having a preselectable coding rate, said method comprising the steps of:
- (a) providing a coding trellis having a plurality of sets of states, and meeting preselected modulation constraints defining for each state in each set a respective threshold equal to the number of valid code subsequences from that particular state to the end of the trellis;
- and
- (b) encoding the input string by comparing a number x corresponding initially to a binary representation of the input to the threshold for a potential next state in a predetermined preferred one of said sets;
- (c) using the result of said comparison,
- (1) determining a next state and an output bit thereof;
- (2) deducting said predetermined one of said thresholds from x if x is greater than or equal to said predetermined threshold to derive a number x' to be used in place of x;
- and
- (d) recursively repeating steps (b) and (c) until n input bits have been encoded.
A method for lexicographically encoding an n-bit input string of binary data, in a state-dependent code, for use on a binary storage channel to provide an output in the form of coded subsequences having a preselectable m/n coding rate, said method comprising the steps of:
- (a) providing a coding trellis having at least two sets of states interconnected by edges with labels;
- (b) while in one state, setting a number x equal to a number i to be encoded, where 0.ltoreq.i<2.sup.m ;
- (c) comparing x to a threshold t determined from preselected modulation constraints corresponding to the number of valid ending subsequences from a state in a preferred successor set to the end of the coding trellis;
- (d) if x<t, following a preselected edge e with an output bit which is the label thereof to said state in said preferred successor set;
- (e) if x.gtoreq.t, following a different edge e with an output bit which is the label thereof to a different state and generating a new number x'=x-t to be used in place of x;
- and
- (f) recursively repeating steps (c) and (d) or (e) until n output bits have been encoded.
A method for lexicographically decoding an n-bit input string of coded bits in a state-dependent code into an n-bit block of user bits comprising the steps of:
- (a) providing a coding trellis having a plurality of sets of states, each state in each set having a respective threshold equal to the number of valid code subsequences from that particular state to the end of the trellis;
- and
- (b) using a succession of the coded bits, determining a path of successive current states through the trellis;
- and
- (c) selectively combining the thresholds for a succession of then current states to provide the n-bit block of user bits in decoded form.
A method for lexicographically decoding to a number x an n-bit coded output string, in a state-dependent code, from a binary storage channel, said method comprising the steps of:
- (a) providing a coding trellis having a plurality of sets of states, each state in each set having a respective threshold equal to the number of valid code subsequences from that particular state to the end of the trellis;
- (b) after initially setting x equal to zero, decoding the input string by conditionally adding to x a succession of predetermined ones of said thresholds;
- (c) by following a path through the coding trellis,
- (1) determining a successor state;
- and
- (2) if the successor state is not in a preferred one of said sets, adding to x the threshold equal to the number of valid code subsequences to the end of the trellis for the state in the preferred one of said sets to derive a number x' to be used in place of x;
- (d) recursively repeating step (c) until all n of the input bits have been decoded;
- and
- (e) outputting the accumulated number x as determined in step (d).
A method for lexicographically decoding to a number x an n-bit input string, in a state-dependent code, from a binary storage channel that provided an output in the form of coded subsequences with a preselectable coding rate, said method comprising the steps of:
- (a) providing a coding trellis having at least two sets of states interconnected by edges with labels;
- (b) while in one state, setting x equal to zero;
- (c) determining, in each set of states, a preferred edge;
- (d) comparing the label of the preferred edge to that of a next input bit;
- (e) if the labels do not correspond, adding a preselected threshold t to x to generate a new number x' to be used in place of x;
- the threshold t being determined from preselected modulation constraints corresponding to the number of valid ending subsequences from a state in a preferred successor set to the end of the coding trellis;
- (f) following the edge label corresponding to the input bit to a successor state;
- (g) recursively repeating steps (c) through (f) until all n outputs of the input bits have been decoded;
- and
- (h) thereafter outputting the number x as determined in step (g).
A method of coding a binary input string to provide an output in NRZ representation meeting, said method comprising the steps of:
- (a) providing a coding trellis having a plurality of sets of states and preselected code paths between said states and preselected modulation constraints defining for each state in each set a respective threshold equal to the number of valid code subsequences from that particular state to the end of the trellis;
- (b) encoding the input string into encoded subsequences;
- and
- (c) whenever a choice of paths is offered, locally reordering said encoded subsequences to give preference to a successor state that permits concatenation of a most recent encoded subsequence with all subsequences from the successor state to the end of the trellis that do no violate the modulation constraints.
Apparatus for lexicographically coding indicia in a state-dependent code between user binary data and a coded sequence thereof, comprising:
- (a) a read only memory providing a coding trellis having a plurality of sets of states, each state in each set having a respective threshold equal to the number of valid code subsequences from that particular state to the end of the trellis;
- (b) means for determining a path through the trellis corresponding to a current state;
- and
- (c) means recursively responsive to the thresholds corresponding to successive current states to provide an invertible mapping between the binary data and the coded sequence.
Dependencies are inferred from the claim text.