Constrained System Endec

Various embodiments of the present invention provide apparatuses and methods for encoding and decoding data for constrained systems with reduced or eliminated need for hardware and time intensive arithmetic operations such as multiplication and division.

DETAILED DESCRIPTION OF THE INVENTION

Various embodiments of the present invention provide apparatuses and methods for encoding and decoding data for constrained systems with reduced or eliminated need for hardware and time intensive arithmetic operations such as multiplication and division. Reducing or eliminating multiplication and division in a constrained system encoder greatly simplifies the hardware design of the encoder and may be achieved with little or no increase in latency.

Turning toFIG. 1, a data processing system100is shown in accordance with various embodiments of the present inventions. Data processing system100includes a processor122that is communicably coupled to a computer readable medium120. As used herein, the phrase “computer readable” medium is used in its broadest sense to mean any medium or media capable of holding information in such a way that it is accessible by a computer processor. Thus, a computer readable medium may be, but is not limited to, a magnetic disk drive, an optical disk drive, a random access memory, a read only memory, an electrically erasable read only memory, a flash memory, or the like. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of computer readable mediums and/or combinations thereof that may be used in relation to different embodiments of the present inventions. Computer readable medium120includes instructions executed by processor122to produce a multiplication and division free constrained system encoder114and a corresponding decoder116. The term “multiplication and division free” is used herein to an encoder in which at least some of the multiplication and division arithmetic operations are performed on integers that are powers of 2 and can therefore be performed using binary shift operations. The term “multiplication and division free” does not preclude the use of some traditional multipliers and dividers, if desired, in conjunction with the shift-based operations. Multiplication and division free constrained system encoder114is provided to an encoding and transmission circuit104, for example as an encoder design to be used in the design of the encoding and transmission circuit104or as an executable encoder. The encoding and transmission circuit104encodes a data input102using multiplication and division free constrained system encoder114to produce a encoded data106. The corresponding decoder116is provided to a receiving and decoding circuit110that decodes encoded data106using decoder116to provide a data output112.

Turning toFIG. 2, a code generation system200is shown in accordance with some embodiments of the present invention. Code generation system200includes a computer202and a computer readable medium204. Computer202may be any processor based device known in the art. Computer readable medium204may be any medium known in the art including, but not limited to, a random access memory, a hard disk drive, a tape drive, an optical storage device or any other device or combination of devices that is capable of storing data. Computer readable medium includes instructions executable by computer202to generate an multiplication and division free constrained system encoder and decoder. In some cases, the instructions may be software instructions. In other cases, the instructions may include a hardware design, or a combination of hardware design and software instructions. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize other types of instructions that may be used in relation to different embodiments of the present inventions.

Turning toFIG. 3, another code generation system300is shown in accordance with other embodiments of the present invention. Code generation system300includes a computer302and a computer readable medium304. Computer302may be any processor based device known in the art. Computer readable medium304may be any medium known in the art including, but not limited to, a random access memory, a hard disk drive, a tape drive, an optical storage device or any other device or combination of devices that is capable of storing data. Computer readable medium includes instructions executable by computer302to generate an multiplication and division free constrained system encoder and decoder. In some cases, the instructions may be software instructions. In other cases, the instructions may include a hardware design, or a combination of hardware design and software instructions. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize other types of instructions that may be used in relation to different embodiments of the present inventions.

In addition, code generation system300includes a simulation integrated circuit306. Simulation integration circuit306may be used to implement and test the multiplication and division free constrained system encoder and decoder, including encoding and decoding test data and providing data characterizing the performance of the encoder and decoder, such as incidence of error and latency information. Based upon the disclosure provided herein, one of ordinary skill in the art will appreciate a variety of distributions of work between computer302executing instructions and simulation integrated circuit306.

Although an encoder and decoder generated as disclosed herein are not limited to use in any particular application, they may be used in a read channel of a storage device. Turning toFIG. 4, a storage system400including a read channel circuit402having a multiplication and division free encoder and decoder is shown in accordance with some embodiments of the present inventions. Storage system400may be, for example, a hard disk drive. Storage system400also includes a preamplifier404, an interface controller406, a hard disk controller410, a motor controller412, a spindle motor414, a disk platter416, and a read/write head420. Interface controller406controls addressing and timing of data to/from disk platter416. The data on disk platter416consists of groups of magnetic signals that may be detected by read/write head assembly420when the assembly is properly positioned over disk platter416. In one embodiment, disk platter416includes magnetic signals recorded in accordance with either a longitudinal or a perpendicular recording scheme.

In a typical read operation, read/write head assembly420is accurately positioned by motor controller412over a desired data track on disk platter416. Motor controller412both positions read/write head assembly420in relation to disk platter416and drives spindle motor414by moving read/write head assembly to the proper data track on disk platter416under the direction of hard disk controller410. Spindle motor414spins disk platter416at a determined spin rate (RPMs). Once read/write head assembly420is positioned adjacent the proper data track, magnetic signals representing data on disk platter416are sensed by read/write head assembly420as disk platter416is rotated by spindle motor414. The sensed magnetic signals are provided as a continuous, minute analog signal representative of the magnetic data on disk platter416. This minute analog signal is transferred from read/write head assembly420to read channel circuit402via preamplifier404. Preamplifier404is operable to amplify the minute analog signals accessed from disk platter416. In turn, read channel circuit402decodes and digitizes the received analog signal to recreate the information originally written to disk platter416. This data is provided as read data422to a receiving circuit. As part of processing the received information, read channel circuit402processes the received signal using a multiplication and division free encoder and decoder. A write operation is substantially the opposite of the preceding read operation with write data424being provided to read channel circuit402. This data is then encoded and written to disk platter416. It should be noted that various functions or blocks of storage system400may be implemented in either software or firmware, while other functions or blocks are implemented in hardware.

Storage system400may be integrated into a larger storage system such as, for example, a RAID (redundant array of inexpensive disks or redundant array of independent disks) based storage system. Such a RAID storage system increases stability and reliability through redundancy, combining multiple disks as a logical unit. Data may be spread across a number of disks included in the RAID storage system according to a variety of algorithms and accessed by an operating system as if it were a single disk. For example, data may be mirrored to multiple disks in the RAID storage system, or may be sliced and distributed across multiple disks in a number of techniques. If a small number of disks in the RAID storage system fail or become unavailable, error correction techniques may be used to recreate the missing data based on the remaining portions of the data from the other disks in the RAID storage system. The disks in the RAID storage system may be, but are not limited to, individual storage systems such as storage system400, and may be located in close proximity to each other or distributed more widely for increased security. In a write operation, write data is provided to a controller, which stores the write data across the disks, for example by mirroring or by striping the write data. In a read operation, the controller retrieves the data from the disks. The controller then yields the resulting read data as if the RAID storage system were a single disk.

Turning toFIG. 5, a data processing system500relying on a multiplication and division free encoder and decoder is shown in accordance with various embodiments of the present invention. Data processing system500includes an encoding circuit506that applies multiplication and division free encoding to an original input502. Original input502may be any set of input data. For example, where data processing system500is a hard disk drive, original input502may be a data set that is destined for storage on a storage medium. In such cases, a medium512of data processing system500is a storage medium. As another example, where data processing system500is a communication system, original input502may be a data set that is destined to be transferred to a receiver via a transfer medium. Such transfer mediums may be, but are not limited to, wired or wireless transfer mediums. In such cases, a medium512of data processing system500is a transfer medium. The multiplication and division free encoder design or instructions are received from a block504that generates a multiplication and division free encoder and decoder as disclosed below based upon constraints to be applied in the system.

Encoding circuit506provides encoded data (i.e., original input encoded using the multiplication and division free encoder) to a transmission circuit510. Transmission circuit510may be any circuit known in the art that is capable of transferring the received encoded data via medium512. Thus, for example, where data processing circuit500is part of a hard disk drive, transmission circuit510may include a read/write head assembly that converts an electrical signal into a series of magnetic signals appropriate for writing to a storage medium. Alternatively, where data processing circuit500is part of a wireless communication system, transmission circuit510may include a wireless transmitter that converts an electrical signal into a radio frequency signal appropriate for transmission via a wireless transmission medium. Transmission circuit510provides a transmission output to medium512.

Data processing circuit500includes a pre-processing circuit514that applies one or more analog functions to transmitted input from medium512. Such analog functions may include, but are not limited to, amplification and filtering. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of pre-processing circuitry that may be used in relation to different embodiments of the present invention. Pre-processing circuit514provides a pre-processed output to a decoding circuit516. Decoding circuit516includes a decoder that is capable of reversing the encoding process applied by encoding circuit506to yield data output520.

A multiplication and division free code for constrained systems which may be encoded and decoded using binary shift operations in place of intensive arithmetic operations such as multiplication and division is generated using directed graphs, or digraphs, which characterize the system constraints. The constraints may, for example, prevent undesirable patterns for a particular storage or transmission medium, such as long runs of 0's or long runs of transitions. A labeled digraph DG=(V, A, L) consists of a finite set of states V=VDG, a finite set of arcs A=ADGwhere each arc e has an initial state σDG(e)εVDGand a terminal state τDG(e)εVDG, and an arc labeling L=LDG: A→H where H is a finite alphabet. A set of all finite sequences obtained from reading the labels of paths in a labeled digraph DG is called a constrained system, S. DG presents S, denoted by S=S (DG).

Turning toFIG. 6, a simple labeled digraph (DG)600is shown having two states, state 1602and state 2604, with paths or edges entering and exiting the states602and604that are labeled to indicate the output value when that path is taken. From state 1602a self-loop612is labeled 0 to indicate that a 0 is output when the system transitions from state 1602back to state 1602in one step. An arc606from state 1602to state 2604is labeled 1, indicating that a 1 is output when the system transitions from state 1602to state 2604. Arc610from state 2604to state 1602is labeled 1. Given a labeled DG600, the output can be determined by taking the paths from state to state. For example, starting from state 1602and taking self-loop612, arc606, arc610and self-loop612yields an output of 0110. In this labeled DG600, 1's are produced in even numbers. When designing a code for a constrained system, a labeled DG can be produced that characterizes the constraint set.

Constraint sequences can be mapped to sequences generated by a labeled DG using symbolic dynamics. In this process, a connectivity matrix is generated for the labeled DG. For the labeled DG600ofFIG. 6, the connectivity matrix is:

where element 1,1 represents the connection612from state 1602to state 1602, element 1,2 represents the connection606from state 1602to state 2604, element 2,1 represents the connection610from state 2604to state 1602, and the 0 in element 2,2 represents the lack of a connection from state 2604to state 2604.

The highest rate code that can be designed from a labeled DG can be computed as log(λ), where λ is the largest real and positive eigenvalue of connectivity matrix. For an eigenvalue λ, there is a vector x that satisfies the equation A*x=λ*x, where A is the connectivity matrix, x is a vector, and λ is the eigenvalue number. If the matrix A is non-negative and real, meaning that there are no complex numbers in the connectivity matrix, and that it contains 0's or positive numbers, then λ is also a real, non-negative number that allows the computation of the highest rate code. If the input block length of the encoder is denoted L, and the output block length is denoted N, where N>L, the encoder can be designed to map the L input bits to N output bits in an invertible manner. Given L input bits, there are 2Linput patterns to be mapped to outputs. Each of the N blocks are referred to as codewords in a codeword space, generally a subset of all the possible output patterns. The resulting encoder has a rate L/N, and the higher the rate, the greater the efficiency of the encoding.

The labeled DG characterizes the constraints and can be used to calculate the code rate, but does not define the mapping between inputs and outputs. The mapping can be performed using a power of a labeled DG. Turning toFIGS. 7A and 7B, another labeled DG700and its 2ndpower DG750are shown to illustrate a possible mapping between input and output patterns. Labeled DG700includes state 1702and state 2704, with arc706from state 1702to state 2704labeled 1, arc710from state 2704to state 1702labeled 0, and self-loop712from state 1702labeled 0. This labeled DG700will not generate two 1's in sequence. If 1's represent transitions, then no two transitions are adjacent.

To map input bits to output bits, a DG may be taken to a power based on the rate and on the number of output bits for each input bit. For example, in a ½ rate code, two output bits are produced for every input bit, and the 2ndpower750of the DG700may be used for the mapping. The 2ndpower DG750of the DG700has the same number of states, state i752and state j754. There is an arc from state i752to state j754in the 2ndpower DG750if there is a path of length two from state 1702to state 2704in DG700. Because state 1702to state 2704in DG700can be reached in two steps on arcs712and706, with labels 0 and 1, 2ndpower DG750includes an arc756labeled 01 from state i752to state j754. Based on the two-step paths in DG700, 2ndpower DG750also includes self-loop760labeled 01 from state j754, arc762labeled 00 from state j754to state i752, self-loop764labeled 00 from state i752and self-loop766labeled 10 from state i752. These labels represent the outputs for each state transition from state i752and state j754.

Input bits can be mapped to the paths in 2ndpower DG750in any suitable manner, including in a somewhat arbitrary manner. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of mapping techniques that may be used to characterize a constrained code from a digraph. Each incoming bit is assigned to a path in 2ndpower DG750, for example assigning incoming bit1when received in state i752to self-loop766, so that when a 1 is received in that state, a 10 is yielded at the output. (The notation 1/10 is used in the label for self-loop766, with the incoming value before the slash and the outgoing value after the slash.) Incoming bit0is assigned when received in state i752to arc756so that when a 1 is received in state i752, a 01 is output. At this point, with incoming bit values 0 and 1 having been mapped for state i752, self-loop764is not needed. Incoming bit values 0 and 1 when received in state j754are assigned to self-loop760and arc762, respectively.

The 2ndpower DG750when labeled defines the encoder, because it describes fully how input bits are mapped to output bits at a rate 1:2, or code rate ½, in an invertible manner that satisfies the constraint of preventing consecutive 1's.

In this simple example, each state752and754had sufficient outgoing edges to map each possible input bit. However, given a DG and its powers, this is often not the case. For example, to design a ⅔ code rate encoder based on labeled DG700, the labeled DG700is taken to the 3rdpower, yielding connectivity matrix

for the 2ndpower and connectivity matrix

for the 3rd power. This indicates that state 1 in the 3rdpower DG will have 5 outgoing edges and state 2 in the 3rdpower DG will have 3 outgoing edges. Given two input bits in the ⅔ code rate encoder, four outgoing edges are needed from each state, and state 2 has too few outgoing edges, preventing the simple mapping of input to output bits in a power of the original DG as inFIGS. 7A and 7B.

State splitting may be used to manipulate the DG to produce another DG that generates the same sequences, but for which every state has at least the necessary number of outgoing edges so that the encoder can be designed by arbitrarily assigning input bits to outgoing edges. State splitting redistributes outgoing edges, taking them from states with an excess and redistributing them to states with insufficient edges until each state has at least the minimum number of outgoing edges to achieve the desired code rate. In general, because λ can be any real number, the x vector may also be a non-integral real number. Given a log(λ) that is at least slightly larger than the desired code rate, a non-negative integer approximate eigenvector can be found that satisfies the equation A*x≧λ*x, where x is a non-negative integer that enables the use of a state splitting algorithm.

In general, state splitting is performed by identifying the largest coordinates of vector x and splitting the corresponding state into a number of smaller states. The outgoing edges from the original state are partitioned into two or more subsets, each of which are assigned to a new state. Each of the new smaller states have the same input as the original state. The resulting digraph thus has more states than the original digraph, with a new approximate eigenvector. In some embodiments, the end result of the state splitting operation is an approximate eigenvector in which every state has a coordinate or weight of 1 or 0, with the number of states equaling the sum of the coordinates of vector x.

If the constraints result in an approximate eigenvector where the sum of the coordinates is a very large number, the resulting encoder can be very complicated, using many multipliers and dividers, which greatly increases hardware complexity. Thus, even when state splitting provides sufficient edges from each state to map input bits to output bits at the desired code rate, traditional mappings may require arithmetic divisions and multiplications for large integers in the encoder. To avoid this, a representation is found for a subset DG* of digraph DG that supports codes that require no multiplication or division, except by powers of 2 that can be performed with binary shift operations.

To identify the subset DG*, the approximate eigenvector AE is generated for digraph DG according to Equation 1:

where T(DG) is the connectivity matrix for digraph DG and AE(DG)′ is an approximate Eigenvector in row vector form corresponding to digraph DG, transposed to yield a column vector. The left side of Equation 1 is a matrix multiplied by a column vector, resulting in a column vector The right side of Equation 1 is a column vector.

If possible, an approximate eigenvector AE is found that satisfies Equation 2:

where P is a real number. Where the largest eigenvector is already 2L, the inequality cannot be satisfied when a real positive number P is added, however, this is uncommon. Because log(λ) is most often a real irrational number, there will be a rational approximation that permits the addition of P.

An approximation AE* to approximate eigenvector AE is identified that satisfies Equation 3:

such that the number of 1's in the binary representation of AE*(i) coordinates does not exceed K for all i states, where K is the maximum number of ones in the binary representation of the coordinates of the approximate eigenvector used in the first stage of the state splitting operation. The coordinates of AE* are integers which, when represented in binary, do not have more than K 1's. P* may be smaller than P due to the approximation performed in finding AE*.

State splitting is applied to digraph DG in two stages. In the first stage, digraph DG is split using AE* such that the approximate eigenvector AE1 of resulting digraph DG1 has an Eigenvector coordinate that is a power of 2. More specifically, each state i in digraph DG is split into at most K states having AE1(state(i,j))=λ(i,j), where λ(i,j) is a power of 2. K is equal to 8 in some embodiments but is not limited to any particular value. As shown inFIG. 8, in the embodiments in which K=8, state i800is split into at most K states (i,1)802, (i,2)804, (i,3)806, (i,4)810, (i,5)812, (i,6)814, (i,7)816, (i,8)820. This is performed by partitioning the outgoing edges of state i800, assigning one group in the partition to new state (i,1)802which takes a subset of the outgoing edges from original state i800. From the remainder of the outgoing edges from original state i800, another state (i,2)804takes another subset of the remaining outgoing edges not already taken by state (i,1)802. When generate state (i,1)802, enough edges are taken so that the weight of that state, or the eigenvector value of that state, is a power of 2. When generating state (i,2)804, enough edges are taken so that its weight is a power of 2. In general, after the stage 1 state splitting operation, there may be a few edges822left which are discarded and not used in the encoder.

The value for K may be established by selecting a value, splitting every state of digraph DG to up to that selected number of states, and finding the largest eigenvector of the resulting digraph, and if it is large enough to satisfy Equation 4, K is large enough, otherwise, K is increased and the process is repeated. Again, in the first stage state splitting digraph DG is split using AE* such that the approximate eigenvector AE1 of resulting digraph DG1 has an Eigenvector coordinate that is a power of 2:

where T1 is the connectivity matrix associated with DG1.

More specifically, the first stage state splitting is performed starting with AE*(i)=λ(i). Letting b denote the base 2 representation of λ(i), b=[b(k) b(k−1) b(k−2) . . . b(2) b(1) b(0)], where b's are binary. The location of 1's in b are specified by j's, where j1>j2> . . . >jq for q≦K. States are split from state i with the following weights or AE1 values:

In the second stage of state splitting, the resulting digraph DG1 may be split using AE1 in any suitable manner, such as with a traditional state splitting algorithm, to yield digraph DG2 with approximate eigenvector AE2, where the weights or coordinates of AE2 are all 0's or 1's. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of state splitting algorithms that may be used in relation to different embodiments of the present inventions to split DG1 using AE1 to yield digraph DG2 with approximate eigenvector AE2, where the weights or coordinates of AE2 are all 0's or 1's.

Because the second stage of state splitting begins with an approximate eigenvector AE1 in which all coordinates are powers of 2, multiplication and division operations needed to implement the code in the resulting encoder and decoder will be performed on integers that are powers of 2. This allows binary shift operations to be used rather than multiplication and division operations, greatly simplifying the encoder and decoder.

The encoder and decoder may then be generated in any suitable manner based on DG2, for example using the mapping of inputs to outputs disclosed above with respect toFIGS. 7A and 7B. Based upon the disclosure provided herein, one of ordinary skill in the art will recognize a variety of techniques that may be used in relation to different embodiments of the present inventions to produce an encoder and decoder based on digraph DG2.

In general, satisfying Equation 3 is straightforward if P* is large enough, and a large P value promotes a large P*. If Equation 3 is satisfied with K=1, then AE1 can be considered to be another approximate eigenvector for DG. Because Equation 2 uses a greater than inequality, the last step of state splitting will have extra edges that are not needed for encoding, due to the approximation of AE in AE*. Each time edges are discarded in a state splitting operation, there is a danger that too many edges will be discarded and there will be insufficient edges remaining to result in the desired code rate. However, K can be increased to a sufficient level to prevent this outcome, and complexity in the implementation of the encoder and decoder due to K is substantially linear. The value P is a measure of the cushion in the extra edges, and if it gets too small as edges are discarded the design will fail. If an AE* is found with a large P*, there will be a relatively larger number of extra edges that can be discarded during the design process, and this can enable the use of a smaller K.

Turning toFIG. 9, the relationship between latency and P is not linear. In graph900, the Y axis902corresponds to latency and the X axis904corresponds to the value of P. Notably, as P increases from one point906to another point910, the latency can actually decrease as P increases until it reaches the point910at which it jumps to another level912. Thus, although in general a larger P promotes a larger P* which is desirable, it also increases AE. Traditionally, constrained system code design has attempted to minimize AE in order to decrease complexity. However, by freeing the encoder and decoder from multipliers and dividers, the system is simplified even though AE is increased, and if AE is not pushed past the threshold at which latency jumps, latency may not be adversely affected by the larger AE.

Turning toFIG. 10, a flow diagram1000depicts a method for generating a constrained systems endec in accordance with various embodiments of the present inventions. Following flow diagram1000, a digraph DG is generated characterizing the constraint set for a constrained system. (Block1002) An approximate eigenvector AE is calculated for DG that satisfies Equation 1. (Block1004) An approximation AE* is calculated for AE such that the number of 1's in the binary representation of AE*(i) does not exceed K for all I, where K is the maximum number of states into which each state in the digraph DG will be split in a first stage of state splitting. (Block1006) A first state splitting stage is performed on DG using AE* to generate digraph DG1 with an approximate eigenvector AE1, where AE1 is a power of 2, and where each state i in DG is split into at most K states. (Block1010) A second state splitting stage is performed on DG1 using AE1 to generate digraph DG2 with an approximate eigenvector AE2, where the weights of AE2 are 0's or 1's. (Block1012) An encoder and decoder are then generated for the constrained code based on DG2. (Block1014)

In one embodiment of the method for generating a constrained systems endec, DG has 67 states such that the connectivity matrix is a 67×67 integer matrix and each arc is labeled by a 36 bit binary sequence in order to design a rate 34/36 code based on DG. An approximate integer eigenvector AE is set forth in Table 1:

Referring to Equation 2, the value of P for the AE in Table 1 is 0.0249, which is too small to result in the desired code rate. One way to increase P is the following:

Starting from Equation 2: T(DG)*AE(DG)′>P+2L*AE(DG)′

2) find a location j in q such that q(j)>1

Repeat step 1 until minimum of q is large enough. Then P equals 2Ltimes the minimum of q.

By increasing P to 67 to provide a larger cushion in the number of edges that can be discarded during the design process, the approximate eigenvector AE is changed to that set forth in Table 2:

In this case, the DG and corresponding approximate eigenvector AE does not have an immediate approximate eigenvector AE* for which coordinates are a power of 2 and satisfying Equation 1 with N=34. Therefore, the first stage state splitting is performed. Although in this case any integers greater than or equal to 7 are candidates for K, and K=8 is selected for ease in state splitting DG to yield DG1. The resulting approximate eigenvectors AE* and AE1 are characterized as follows:

for 1≦i≦67, and 1≦j≦8. Notably, if JB(i,j)=0, there is no state (i,j).

JB(i,j) is given in Table 3, specifying the position of the 1's in AE*(i). Again, the number of 1's in the binary representation of AE*(i) does not exceed K for all i states, in this case in all 8 states.

The location of the 1's in AE*(i) is specified by 2̂35−j. Thus, for state i=1, j=1, Table 3 indicates that the first 1 in state 1 is at 2̂(35−1), or 2̂34. The second 1 in state 1 is at position 2̂(35−4) or 2̂31.

The digraph DG is then split using AE* in a second stage state splitting operation as disclosed above to yield DG1. If P* in Equation 3 is greater than or equal to K, the splitting from DG to DG1 can be performed in one round of state splitting. Thus, because P≧8, the splitting from DG to DG1 can be performed in one round of state splitting, although it is not necessary that this condition be satisfied.

The desired encoder/decoder is then generated by applying the second stage of state splitting from DG1 to DG2, followed by generating the encoder/decoder based on DG2. The resulting 34/36 code can be applied in the encoder and decoder using binary shift operations rather than multiplication and division operations, greatly simplifying the hardware design or computer execution of the encoder and decoder.

In conclusion, the present invention provides novel apparatuses and methods for encoding and decoding data for constrained systems with reduced or eliminated need for hardware and time intensive arithmetic operations such as multiplication and division. While detailed descriptions of one or more embodiments of the invention have been given above, various alternatives, modifications, and equivalents will be apparent to those skilled in the art without varying from the spirit of the invention. Therefore, the above description should not be taken as limiting the scope of the invention, which is defined by the appended claims.