Sequential encoding and decoding of variable word length, fixed rate data codes

A method of encoding by electrical circuitry on a bit by bit basis a first string of binary bits representing sequential data words of a variable word length code into a second run length limited string of binary bits representing sequential fixed rate code words of variable length, said method comprising the steps of:

• (1) generating by electrical circuitry a plurality of electrical signals representing the binary values of the first three bit positions of said first string;
• (2) generating by electrical circuitry an electrical control signal by logically combining in electrical circuitry a preselected group of said plurality of electrical signals, said electrical control signal providing an indication of the boundary between a first variable length data word and the next data word;
• (3) generating by electrical circuitry an electrical signal representing the encoded value of the first bit position of said second string by logically combining in electrical circuitry said electrical control signal with a second preselected group of said plurality of electrical signals including the electrical signal corresponding to said first bit position of said first three bit positions of said first string;
• (4) generating by electrical circuitry an electrical signal representing the value of the second bit position of said second string by logically combining in electrical circuitry said electrical control signal with a third preselected group of said plurality of electrical signals including the electrical signal representing the second bit position of said first three bit positions of said first string;
• and
• (5) repeating steps 1-4 for each succeeding new combination of three adjacent bit positions (2-3-4, 3-4-5, etc.) until the last bit position of said first string is encoded.

A method of encoding by electrical circuitry on a bit by bit basis a first string of binary bits representing a sequence of variable length data words predefined by a first dictionary containing data words whose lengths vary from 2 to 4 bit positions into a second string of binary bits representing a sequence of variable length code words, each bit of each data word of said first string being represented by two bits in said second string, said second string being a 2-7 run length limited sequence,

• said method comprising:
• (1) generating by electrical circuitry a plurality of binary electrical signals corresponding to the true values and complemented values of the first three bit positions of said first string;
• (2) generating by electrical circuitry an electrical control signal by combining in electrical circuitry selected ones of said plurality of binary signals in accordance with predefined logic to provide an indication of the presence of a word boundary between adjacent bit positions of said first three bit positions;
• (3) logically combining in electrical circuitry the true and complement electrical signals corresponding to the value of said first bit position with selected ones of said true and complement electrical signals from said other two bit positions and said electrical control signal to generate an encoded electrical signal corresponding to the first encoded bit of said second string;
• (4) logically combining in electrical circuitry said control signal with an electrical signal corresponding to the value of said second bit position to generate an encoded electrical signal corresponding to the second encoded bit of said second string;
• and
• (5) repeating steps 1-4 for the next new combination of three bit positions of said first string (2, 3 and 4) and each successive new combination of said first string until the last bit of said first string has been encoded.

A method of encoding by electrical circuitry on a bit sequential basis a first string of binary bits representing sequential multi-bit data words belonging to a predefined dictionary of data words, said data words having a minimum of two bits and a maximum of four bits, into a second string of binary bits representing sequential multi-bit code words corresponding to said sequential multi-bit data words in accordance with said predefined dictionary, each of said code words having twice as many bits as its corresponding data word,

• said method comprising:
• (1) generating by electrical circuitry a group of electrical signals representing the binary values of the first three positions of said first string;
• (2) generating by electrical circuitry a word ending electrical signal by logically combining in circuitry electrical signals selected from the first and second said positions of said group to indicate if the length of said first word is two bits, three bits or four bits in length;
• (3) encoding by electrical circuitry the first bit of said first string into the first two bits of said second string when said indicator signal identifies a two bit data word by logically combining in electrical circuitry selected electrical signals from said group with said indicator electrical signal and encoding the second bit of said two bit word as two zeros, regardless of the value of said second bit;
• or
• (4) encoding by electrical circuitry the first bit of said first string into the first two bits of said second string when said indicating signal indicates a three bit data word by logically combining in electrical circuitry said three bit indicating electrical signal with the electrical signals from said group corresponding to the values of said first and third bits, and
• (5) encoding by electrical circuitry the second bit of said first string into the second two bits of said second string when said indicating electrical signal indicates a three bit data word by logically combining in electrical circuitry said three bit indicator electrical signal with selected electrical signals from said group corresponding to the values of said second and third positions and encoding by electrical circuitry the last bit of said data word into two zeros by logically combining in electrical circuitry the electrical signal from said group corresponding to the value of said third position with said three bit indicating signal;
• or
• (6) encoding by electrical circuitry the first bit of said first string into two zeros of said second string when said indicating electrical signal indicates a four bit data word by combining in electrical circuitry said four bit word indicating electrical signal with an electrical signal from said group corresponding to the value of said first bit position;
• (7) generating by electrical circuitry a second group of electrical signals representing the values of the next new combination of three bit positions (2, 3 and 4) of said first string;
• (8) generating by electrical circuitry a second indicator electrical signal from said second group of electrical signals to indicate the length of code words;
• (9) encoding by electrical circuitry the second bit of said first four bit word into the second two bits of said second string by logically combining in electrical circuitry said second indicator electrical signal and electrical signals from said second group corresponding to the values of said second and fourth positions of said string;
• (10) encoding by electrical circuitry the third bit of said first four bit word into the third two bits of said second string by logically combining in electrical circuitry said second indicator electrical signal and the electrical signals from said second group corresponding to the values of said third and fourth positions of said string;
• (11) encoding by electrical circuitry the last bit of said first four bit word into two zeros to form the last two bits of said first code word by logically combining in electrical circuitry a signal from said second group corresponding to the value of said fourth position with said second indicator electrical signal;
• and
• (12) repeating the above steps for each successive data word in said first string.

Apparatus for converting bit signals representative of binary data in one form to bit signals representative of the same data in another form according to a run-length-limited variable word length code wherein one of said forms is a coded form in which only a predetermined plurality of bit signal patterns of differing lengths are valid code words, said code also being of fixed rate so that each of said code words in said coded form corresponds to a respective predetermined word of directly proportional length in said other form;

• said apparatus comprising:
• input shift register means arranged to receive input bit signals in one of said forms serially at an input signal rate and having a plurality of stages for storing said input bit signals;
• clocking means for providing clock signals in synchronism with said input bit signals and being connected to said input shift register means to shift said input bit signals progressively therethrough at said input signal rate;
• word position storage means for storing information indicating the position of a word boundary relative to said input shift register means;
• updating means responsive to said input shift register means and said word position storage means for updating said word position storage means as said input bit signals are shifted through said input shift register means;
• conversion logic means, connected to said input shift register means and said word position storage means, for converting a fixed number of bit signals in one of said forms, stored in a predetermined portion of said input shift register means, into a corresponding number of output bit signals in the other of said forms according to said variable word length code, said fixed number of bit signals being less than the number of bit signals in the longest input bit signal variable length word;
• and
• output gating means responsive to said clock signals to gate said output bit signals successively to an output at an output signal rate related to said input signal rate by said fixed rate of said code.

Apparatus for encoding input data bit signals according to a run-length-limited variable word length code in which only a predetermined plurality of encoded bit signal patterns of differing lengths are valid code words, said code also being of fixed rate so that each of said code words corresponds to a respective predetermined word of directly proportional length in said input bit signals;

• said apparatus comprising:
• input shift register means arranged to receive input bit signals serially at an input signal rate and having a plurality of stages for storing said input bit signals;
• clocking means for providing clock signals in synchronism with said input bit signals and being connected to said input shift register means to shift said input bit signals progressively therethrough at said input signal rate;
• word position storage means for storing information indicating the position of a word boundary relative to said input shift register means;
• updating means responsive to said input shift register means and said word position storage means for updating said word position storage means as said input bit signals are shifted through said input shift register means;
• encoding logic means, connected to said input shift register means and said word position storage means, for encoding a fixed number of bit signals, stored in a predetermined portion of said input shift register means, into a corresponding number of output bit signals according to said variable word length code, said fixed number of bit signals being less than the number of bit signals in the longest input bit signal variable length word;
• and
• output gating means responsive to said clock signals to gate said encoded output bit signals successively to an output at an output signal rate related to said input signal rate by said fixed rate of said code.

Apparatus for decoding sequentially a plurality of pairs of associated bit signals coded in a (2,7) run length limited variable word length code, each of said pairs of coded bit signals corresponding to one decoded bit signal, and said code being such that valid code words terminate in a word ending sequence of at least four bit signals which is distinct from any other two adjacent associated pairs of coded bit signals;

• said apparatus comprising:
• coded bit signal shift register means having at least eight stages, designated a through h, sufficient to store said word ending sequence in a plurality of said stages, comprising stages d through a, which follow stages e and f, and being arranged to receive said coded bit signals at a coded bit signal rate;
• clocking means for providing clock signals in synchronism with said coded bit signals and being connected to said coded bit signal shift register means to shift said coded bit signals progressively therethrough at said coded bit signal rate in a direction from stage h to stage a;
• and
• decoding logic means responsive to the contents of predetermined stages of said coded bit signal shift register means to generate a decoded bit signal corresponding to the coded bit signals stored in stages e and f of said shift register means;
• said decoding logic means comprising:
• first logic circuit means connected to a first group of predetermined stages of said shift register means and responsive to at least the presence of said distinct word ending sequence in said plurality of stages, comprising stages d through a, to provide at least a first output signal;
• second logic circuit means connected to a second group of predetermined stages of said shift register means and responsive to other predetermined conditions of said shift register means to produce at least a second output signal;
• and
• third logic circuit means for logically combining at least said first and second output signals to produce said decoded bit signal;
• said apparatus further comprising output gating means responsive to said clock signals to gate successive decoded bit signals to an output at a decoded bit signal rate which is half said coded bit signal rate.