Multi-dimensional coding for error reduction

Abstract

A stream of binary bits is converted into blocks of eight parallel bits. A first group of five of the eight bits addresses a memory device which has thirty-two code words each having four numbers representing the coordinates of signal points in four-dimensional space. The remaining three of the eight bits are expanded to four bits by a convolutional encoder having three bits of memory. These four bits are then used to multiply the four numbers of a code word read out from the memory device. This method permits a block of eight binary bits to be coded into any one of five hundred and twelve four-dimensional code words.

What is claimed is: 
     
       1. A method for coding information comprising the steps of separating said information into first and second groups of signals,   addressing any one of a plurality of multidimensional code words by said first group of signals, and   determining the sign of each .[.componet.]. .Iadd.component .Iaddend.of said multidimensional code words by said second group of signals.   
     
     
       2. The method of claim 1 for coding information wherein said multi-dimensional code words are four-dimensional code words. 
     
     
       3. The method of claim 2 for coding information wherein said information comprises a block of eight binary bits, said first group comprises five of said eight binary bits, and said second group comprises the other three of said eight binary bits. 
     
     
       4. The method of claim 3 for coding information wherein said four-dimensional code words consist of a set of thirty-two four-dimensional code words stored in a memory device and each of said four-dimensional code words consist of a subset of four numbers which represent the coordinates of a signal point in four-dimensional space. 
     
     
       5. The method of claim 4 for coding information further comprising the step of converting binary 1's to -1's and binary 0's to 1's for said first group of signals prior to addressing said four-dimensional code words. 
     
     
       6. The method of claim 5 for coding information further comprising the steps of expanding the number of bits in said second group of signals from three to four in a convolutional encoder comprising three bits of memory, and converting the binary 1's to -1's and binary 0's to 1's.   
     
     
       7. The method of claim 6 further comprising the step of multiplying each of said components of said four-dimensional code word by said expanded and converted second group of signals, thereby deriving any one of five hundred and twelve encoded four-dimensional symbols for each input block of eight binary signals. 
     
     
       8. The method of claim 2 for coding information wherein said information comprises a block of twelve binary bits, said first group comprises nine of said binary bits and said second group comprises the other three of said twelve binary bits. 
     
     
       9. The method of claim 8 for coding information wherein said four-dimensional code words consist of a set of five hundred and twelve four-dimensional code words stored in a memory device and each of said four-dimensional code words consist of a subset of four numbers which represent the coordinates of a signal point in four-dimensional space. 
     
     
       10. The method of claim 9 for coding information further comprising the step of converting binary 1's to -1's and binary 0's to 1's for said first group of signals prior to addressing said four-dimensional code words. 
     
     
       11. The method of claim 10 for coding information further comprising the steps of expanding the number of bits in said second group of signals from three to four in a convolutional encoder comprising three bits of memory, and   converting the binary 1's to -1's and binary 0's to 1's.   
     
     
       12. The method of claim 11 for coding information further comprising the step of multiplying each of said components of said four-dimensional code word by said expanded and converted second group of signals, thereby deriving any one of eight thousand, one hundred and ninety-two encoded four-dimensional symbols for each input block of twelve binary signals. 
     
     
       13. Apparatus for coding information comprising means for converting a predetermined plurality of serial binary bits into parallel bits, said parallel bits being separated into first and second groups of signals,   means for converting the binary 1's to -1's and binary 0's to 1's for said first group of signals which are then used for addressing any one of a plurality of multi-dimensional code words said code words being stored in a memory device, and said second group of signals being used for determining the sign of each component of said multi-dimensional code words after said code words are read out from said memory device.   
     
     
       14. The apparatus of claim 13 wherein said multidimensional code words are four-dimensional code words, each code word comprising four numbers representing the coordinates of a signal. 
     
     
       15. The apparatus of claim 14 comprising a convolutional encoder which comprises means for storing a plurality of bits for expanding the number of bits in said second group of signals, by one, and   means for converting the expanded bits from binary 1's to -1's and binary 0's to 1's.   
     
     
       16. The apparatus of claim 15 wherein said memory device is a read only memory. 
     
     
       17. The apparatus of claim 16 for coding information comprising means for multipling each component of the code words from said read only memory by said expanded and converted second group of signals to derive an encoded four-dimensional symbol for each block of information. 
     
     
       18. The apparatus of claim 17 wherein said predetermined plurality of serial binary comprises a block of eight binary bits,   said first group comprises five bits of said eight bits,   said means for storing a plurality of bits in said convolutional encoder having a capacity for storing three bits,   said second group comprises the other three of said eight binary bits,   said three bits being the input to said convolutional encoder, the output from said convolutional encoder being four bits, said read only memory comprises a set of thirty-two four-dimensional code words, and   said encoded symbols being any one of a signal constellation comprising five hundred and twelve four-dimensional code words.   
     
     
       19. The apparatus of claim 17 wherein said predetermined plurality of serial binary bits comprises a block of twelve binary bits,   said first group of signals comprises nine bits of said twelve binary bits,   said means for storing a plurality of bits in said convolutional encoder having a capacity for storing three bits,   said second group comprises the other three bits of said twelve binary bits as the input to said convolutional encoder, the output from the convolutional encoder being four bits,   said read only memory comprises a set of five hundred twelve four-dimensional code words, and   said encoded symbols being any one of a signal constellation comprising eight thousand, one hundred and ninety-two four-dimensional code words.   
     
     
       20. Apparatus for coding an input of eight binary bits to any one of five hundred and twelve code words each code word having four numbers representing the coordinates of signal points in four-dimensional space said apparatus comprising a read only memory comprising thirty-two of said four dimensional code words,   a serial-to-parallel converter for converting a serial stream of blocks of eight binary bits into sequences of eight parallel bits, five of said eight parallel bits being used to address any one of said thirty-two code words in said read only memory after passing through a means for converting binary 1's to -1's and binary 0's to 1's, the remaining three bits of said eight parallel bits being the input to a convolutional encoder having three bits of memory,   said convolutional encoder being used to expand said three bits of input to four bits of output,   means for converting said four bits of output from said convolutional encoder from binary 1's to -1's and from binary 0's to 1's, and   means for multiplying each component said four numbers from said read only memory by said four output bits from said convolutional encoder to derive any one of said five hundred and twelve four dimensional code words. .Iadd.   
     
     
       21.  A method for coding information comprising the steps of separating said information into first and second groups of signals,   encoding the signals in said second group to provide an expanded group of signals,   addressing any one of a plurality of multidimensional code words by said first group of signals, and   determining the sign of each component of said multi-dimensional code words by said expanded group of signals. .Iaddend. .Iadd.22. A method for coding information to generate an output code word, said method comprising the steps of   separating said information into first and second groups of signals,   encoding the signals in said second group to provide an expanded group of signals,   identifying one of a plurality of multi-dimensional code words in response to said first group of signals, and   generating said output code word by changing the sign of at least one of the components of said identified code word as a function of said expanded group of signals. .Iaddend. .Iadd.23. A method for generating output code words in response to successive blocks of input signals, each of said blocks comprising first and second groups of said input signals, said method comprising the steps of   identifying for each one of said blocks, and in response to said first group of signals of that block, one of a predetermined plurality of multidimensional code words   generating an individual one of said output code words by changing the sign of at least a selected one of the components of said one of said code words in response to a plurality of trellis coded signals, said trellis coded signals being a function of (a) the signals of the second group of signals of said one of said blocks and (b) at least one bit of the second group of signals of a previous one of said blocks. .Iaddend. .Iadd.24. A method for generating a sequence of output signals in response to a sequence of multidigit input words, each of said output signals representing a respective signal point (x 1 , x 2 , x 3 , x 4 ) of a predetermined alphabet of four-dimensional signal points, said method comprising the steps of   identifying, in response to the values of a selected number of digits of each input word in said input word sequence and the value of at least one digit of a previous input word in said input word sequence, one of a plurality of sets of said signal points, the number of said sets being greater than 2 raised to said selected number, and, in each said set, x 1 , x 2 , x 3  and x 4  being, for all the points in that set, congruent, modulo a predetermined number, to w 1 , w 2 , w 3  and w 4 , respectively, w 1 , w 2 , w 3  and w 4  being predetermined integers each having a value associated with said each set,   identifying, in response at least to the digits of said each input word other than said selected number of digits, a particular one of the signal points of said one set, and   generating as an individual one of said sequence of output signals a signal   
     
     
        representing the identified signal point. .Iaddend. .Iadd.25.  The invention of claim 24 wherein w 1 , w 2 , w 3  and w 4  can each take on one of the two values +1 and -1, wherein x 1 , x 2 , x 3  and x 4  are all odd integers and wherein said predetermined number is 4. .Iaddend. .Iadd.26. A method for generating a sequence of output signals in response to a sequence of binary input words, each of said output signals representing a respective signal point of a predetermined alphabet of multi-dimensional signal points, said signal points being at least of dimension four, said method comprising the steps of identifying, in response to the values of a selected number of bits of each input word in said input word sequence and the value of at least one bit of a previous input word in said input word sequence, one of a plurality of sets of said signal points, the number of said sets being greater than 2 raised to said selected number, said plurality of sets comprising a first set of said signal points and a plurality of further sets of said signal points, each of the points in each said further set being given by a predetermined pattern of sign changes associated with said further set applied to the coordinates of the signal points of said first set,   identifying, in response at least to the bits of said each input word other than said selected number of bits, a particular one of the signal points of said one set, and   generating as an individual one of said sequence of output signals a signal   
     
     
        representing the identified signal point. .Iaddend. .Iadd.27.  Apparatus for generating output code words in response to successive blocks of input bits, each of said blocks comprising first and second groups of said input bits, said apparatus comprising means for identifying for each one of said blocks and in response to said first group of bits of that block, one of a predetermined plurality of multidimensional code words,   means for generating an individual one of said output code words by changing the respective signs of selected ones of the components of said one of said code words in response to a plurality of trellis coded bits, said trellis coded bits being a function of (a) the bits of the second group of bits of said one of said blocks and (b) at least one bit of the second group of bits of a previous one of said blocks. .Iaddend. .Iadd.28. A data transmitter adapted to generate a sequence of output signals in response to a sequence of binary input words, each of said output signals representing a respective signal point (x 1 , x 2 , x 3 , x 4 ) of a predetermined alphabet of four-dimensional signal points, said transmitter comprising   means responsive to the values of a selected number of bits of each input word in said input word sequence and the value of at least one bit of a previous input word in said input word sequence for identifying one of a plurality of sets of said signal points, the number of said sets being greater than 2 raised to said selected number, and, in each said set, x 1 , x 2 , x 3  and x 4  being, for all the points in that set, congruent, modulo a predetermined number, to w 1 , w 2 , w 3  and w 4 , respectively, w 1 , w 2 , w 3  and w 4  being predetermined integers each having a value associated with said each set,   means responsive at least to the bits of said each input word other than said selected number of bits for identifying a particular one of said signal points of said one set, and   means for generating as an individual one of said sequence of output signals a signal representing the identified signal point. .Iaddend. .Iadd.29. The invention of claim 28 wherein w 1 , w 2 , w 3  and w 4  can each take on one of the two values +1 and -1, wherein x 1 , x 2 , x 3  and x 4  are all odd integers and wherein said predetermined number is 4. .Iaddend. .Iadd.30. A data transmitter adapted to generate a sequence of output signals in response to a sequence of multidigit input words, each of said output signals representing a respective signal point of a predetermined alphabet of multi-dimensional signal points, said signal points being at least of dimension four, said transmitter comprising   means responsive to the values of a selected number of digits of each input word in said input word sequence and the value of at least one digit of a previous input word in said input word sequence for identifying one of a plurality of sets of said signal points, the number of said sets being greater than 2 raised to said selected number, said plurality of sets comprising a first set of said signal points and a plurality of further sets of said signal points, each of the points in each said further set being given by a predetermined pattern of sign changes associated with said further set applied to the coordinates of the signal points of said first set,   means responsive at least to the digits of said each input word other than said selected number of digits for identifying a particular one of the signal points of said one set, and   means for generating as an individual one of said sequence of output signals a signal representing the identified signal point. .Iaddend.