DATA ENCODING PROCESS, DATA DECODING PROCESS, COMPUTER-READABLE RECORDING MEDIUM STORING DATA ENCODING PROGRAM, AND COMPUTER-READABLE RECORDING MEDIUM STORING DATA DECODING PROGRAM

• US 20110115654A1
• Filed: 11/16/2010
• Published: 05/19/2011
• Est. Priority Date: 11/17/2009
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Sato, Yuichi, KAMEYAMA, Hiroaki
• Granted Patent: US 8,184,024 B2
• Time in Patent Office: Days
• US Class Current: 341/55
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

In a data encoding process: data is encoded by using unit bit series obtained from an encoding bit series; the encoding bit series is searched for a first bit series identical to a portion of the encoded data; the portion is substituted with a second bit series which includes a leading code indicating a leading position of a substitution range and position information indicating the position of the first bit series in the encoding bit series. In a data decoding process: the position information is detected from the substitution range in received data after the leading code is detected in the data; a substitution bit series is extracted from the position in the encoding bit series indicated by the position information; and the data in the substitution range is substituted with the substitution bit series so as to restore the encoded data.

Claims

1. A non-transitory computer-readable recording medium which stores a data encoding program to be executed by a computer, said data encoding program makes the computer execute a procedure, the procedure comprising:

obtaining encoded data on the basis of data to be encoded and unit bit series which are obtained from an encoding bit series;

searching said encoding bit series for a first bit series identical to a portion of said encoded data; and

substituting the portion of the encoded data with a second bit series, where the second bit series is a combination of a leading code and position information, the leading code indicates a leading position of a substitution range, and the position information indicates a position of the first bit series in the encoding bit series.

2. The non-transitory computer-readable recording medium according to claim 1, wherein in the case where said encoded data other than said portion contains a third bit series which is identical to said leading code, in said substituting, the third bit series is substituted with a discrimination code realized by a fourth bit series different from the third bit series.

3. The non-transitory computer-readable recording medium according to claim 2, wherein said leading code and said discrimination code contain a common partial bit series beginning from a leading bit and a bit following the common partial bit series, the bit following the common partial bit in each of the leading code and the discrimination code has a different value, and the common partial bit series is substituted with the discrimination code in said substituting in the case where said encoded data other than said portion contains a bit series identical to the common partial bit series.

4. The non-transitory computer-readable recording medium according to claim 1, wherein the number of bits constituting said first bit series is variable, said portion of the encoded data is substituted with a third bit series in said substituting, and the third bit series is a combination of said leading code, said position information, and length information indicating a length of said first bit series.

5. The non-transitory computer-readable recording medium according to claim 1, wherein said encoding bit series is prepared as an encoding matrix in which each of said unit bit series is arrayed in a row, said encoding matrix is searched along a variable direction in said searching, said portion of the encoded data is substituted with a third bit series in said substituting, and the third bit series is a combination of said leading code, said position information, and direction information indicating a direction along which said encoding matrix is searched.

6. The non-transitory computer-readable recording medium according to claim 1, wherein, in said obtaining, said unit bit series are cut out from said encoding bit series and each have an identical number of bits, calculations in which data pieces and ones of the unit bit series are combined are performed for producing said encoded data, the encoded data contains results of the calculations and unit-bit-series information items, the unit-bit-series information items are the unit bit series used in the calculations or unit-bit-series position indicators indicating positions, in the encoding bit series, of the unit bit series used in the calculations, the data pieces are produced by division of said data to be encoded and each have a predetermined number of bits, and the results of the calculations are respectively contained in the calculation-result containing regions in the encoded data;

and said searching and said substituting are performed on each of the calculation-result containing regions.

7. The non-transitory computer-readable recording medium according to claim 6, said procedure further comprising:

including each of said calculation-result containing regions in a packet to be transmitted.

8. The non-transitory computer-readable recording medium according to claim 1, wherein, in said obtaining, said unit bit series are n unit bit series each having m bits (where n and m are integers satisfying n≧

m, and m is equal to or greater than one), said data to be encoded is divided into divided-data groups each containing m data pieces, bits in each of the n unit bit series are brought into correspondence with the m data pieces in each of the divided-data groups, one or more of the m data pieces in said each of the divided-data groups, respectively corresponding to one or more “

1”

bits in each of the n unit bit series, are selected, an exclusive OR calculation of the one or more of the m data pieces is performed for each of the n unit bit series and each of the divided-data groups, said encoded data contains, for said each of the n unit bit series and said each of the divided-data groups, a result of the exclusive OR calculation and a unit-bit-series information item which is one of the unit bit series used in the exclusive OR calculation or a unit-bit-series position indicator indicating a position, in said encoding bit series, of said one of the unit bit series used in the exclusive OR calculation, and said encoded data is contained in data regions each of which contains a result of at least one exclusive OR calculation; and

said searching is performed on each of the data regions.

9. The non-transitory computer-readable recording medium according to claim 1, wherein, in said obtaining, said data to be encoded is divided into data pieces each having m bits (where m is an integer equal to or greater than one) b₀, b₁, b₂, . . . , b_m−

1, said unit bit series are n unit bit series each having bits a_i0, a_i2, . . . , a<sub>i(m−

1)</sub> (where n is an integer equal to or greater than m, and i is an integer satisfying 0≦

i≦

n−

1), n solutions p_i (0≦

i≦

n−

1) of a set of simultaneous Boolean equations

b₀a_i0+b₁a_i1+b₂a_i2+ . . . +b<sub>3−

1</sub>a<sub>i(m−

1)</sub>=p_i(0≦

i≦

n−

1)

are obtained by substituting each of the data pieces having bits b_i0, b_i1, . . . , b<sub>i(m−

1)</sub> and the n unit bit series a_i0, a_i1, a_i2, . . . , a<sub>i(m−

1)</sub> into the set of simultaneous Boolean equations, and said encoded data contains all solutions of the set of simultaneous Boolean equations obtained from all the data pieces corresponding to the data to be encoded and unit-bit-series information items, the unit-bit-series information items are the unit bit series used for obtaining all the solutions corresponding to the data to be encoded or unit-bit-series position indicators indicating positions, in said encoding bit series, of the unit bit series used for obtaining all the solutions corresponding to the data to be encoded, and said encoded data is contained in data regions each of which contains at least a predetermined number of ones of all the solutions corresponding to the data to be encoded; and

said searching is performed on each of the data regions.

10. A non-transitory computer-readable recording medium which stores a data decoding program to be executed by a computer, said data decoding program makes the computer execute a procedure, the procedure comprising:

detecting position information from a substitution range in compressed and encoded data which is inputted into the computer, when the leading code is detected in the compressed and encoded data, and the leading code is located at a leading position of the substitution range and indicates the leading position;

extracting a substitution bit series from a position in an encoding bit series indicated by said position information;

substituting a portion of said compressed and encoded data in said substitution range with said substitution bit series so as to restore encoded data; and

restoring original data from said encoded data and unit bit series obtained from said encoding bit series.

11. The non-transitory computer-readable recording medium according to claim 10, wherein when a discrimination code which is a predetermined bit series different from said leading code is detected in said compressed and encoded data, the discrimination code is substituted with the leading code in said substituting.

12. The non-transitory computer-readable recording medium according to claim 11, wherein said leading code and said discrimination code contain a common partial bit series beginning from a leading bit and a bit following the common partial bit series, and the bit following common partial bit in each of the leading code and the discrimination code has a different value.

13. The non-transitory computer-readable recording medium according to claim 10, wherein length information, as well as said position information, is detected from said substitution range in said detecting, and a bit series being located in said position in the encoding bit series indicated by said position information and having a bit length indicated by the length information is extracted as said substitution bit series in said substituting.

14. The non-transitory computer-readable recording medium according to claim 10, wherein said encoding bit series is prepared as an encoding matrix in which each of said unit bit series is arrayed in a row, direction information, as well as said position information, is detected from said substitution range in said detecting, and a bit series being located in a position in the encoding matrix indicated by said position information and being arrayed along a direction indicated by the length information is extracted as said substitution bit series in said substituting.

15. The non-transitory computer-readable recording medium according to claim 10, wherein in said restoring, unit-bit-series information items are extracted from said encoded data, calculation results, which are obtained when the original data is encoded on the basis of the unit bit series and data pieces being produced by division of the original data and grouped into groups of one or more data pieces and each having a predetermined number of bits, are extracted from the encoded data, and each group of one or more data pieces is restored by using part of the calculation results which are obtained on the basis of said each group of one or more data pieces and the unit bit series based on said unit-bit-series information items, where the unit-bit-series information items are the unit bit series per se or unit-bit-series position indicators indicating positions of the unit bit series in the encoding bit series.

16. The non-transitory computer-readable recording medium according to claim 15, wherein said compressed and encoded data inputted into the computer includes calculation-result containing regions each of which contains a part of said calculation results obtained on the basis of one of said unit bit series and at least one of said data pieces produced by the division of the original data, the compressed and encoded data is inputted into the computer in packets, said process further comprises extracting, from each of the packets inputted into the computer, data contained in one of the calculation-result containing regions, and an operation of detecting said leading code is performed for each of the calculation-result containing regions in said detecting.

17. The non-transitory computer-readable recording medium according to claim 15, wherein said unit bit series each have a length of m bits (where m is an integer equal to or greater than one);

and in said restoring, values of bits of m unit bit series based on m unit-bit-series information items which are extracted from said encoded data are arrayed in a matrix arrangement in a first matrix, values of bits of m calculation results obtained on the basis of said each group of one or more data pieces and the m unit bit series are arrayed in a matrix arrangement in a second matrix, a first operation for transforming the first matrix into an identity matrix is performed on the first matrix, and said each group of one or more data pieces is restored by performing on the second matrix a second operation identical to the first operation.

18. The non-transitory computer-readable recording medium according to claim 15, wherein, each of said data pieces produced by division of the original data has m bits (where m is an integer equal to or greater than one) b₀, b₁, b₂, . . . , b_m−

1, m unit bit series a_i (0≦

i≦

m−

1) indicated by m unit-bit-series information items each have m bits a_i0, a_i1, a_i2, . . . , a<sub>i(m−

1)</sub>, and said each of said data pieces is restored, in said restoring, by substituting the m unit bit series a_i and m solutions p_i (0≦

i≦

m−

1) of a set of simultaneous Boolean equations

b₀a_i0+b₁a_i1+b₂a_i2+ . . . +b<sub>m−

1</sub>a<sub>i(m−

1)</sub>=p_i(0≦

i≦

m−

1)

into the set of simultaneous Boolean equations, where the m solutions pi are obtained on the basis of said each of the data pieces and the m unit bit series.

19. A data encoding process comprising:

obtaining encoded data on the basis of data to be encoded and unit bit series which are obtained from an encoding bit series;

searching said encoding bit series for a first bit series identical to a portion of said encoded data; and

substituting the portion of the encoded data with a second bit series, where the second bit series is a combination of a leading code and position information, the leading code indicates a leading position of a substitution range, and the position information indicates a position of the first bit series in the encoding bit series.

20. A data decoding process comprising:

detecting position information from a substitution range in compressed and encoded data which is inputted into the computer, when the leading code is detected in the compressed and encoded data, and the leading code is located at a leading position of the substitution range and indicates the leading position;

extracting a substitution bit series from a position in an encoding bit series indicated by said position information;

substituting a portion of said compressed and encoded data in said substitution range with said substitution bit series so as to restore encoded data; and

restoring original data from said encoded data and unit bit series obtained from said encoding bit series.