DIGITAL DATA COMPRESSION

Abstract

A method for compressing digital data, including: extrapolating a value of each sample of data to be compressed as a function of a value of at least one preceding sample, to produce an extrapolated sample; differentiating between each extrapolated sample and the corresponding sample of data to be compressed, to produce a differentiated sample; and deleting redundancy between successive differentiated samples produced by the differentiating stage.

Claims

1-10. (canceled)

11: A method for compressing digital data, comprising: extrapolating a value of each sample of data to be compressed as a function of a value of at least one preceding sample, to produce an extrapolated sample; differentiating between each extrapolated sample and a corresponding sample of data to be compressed, to produce a differentiated sample; deleting redundancy between successive differentiated samples produced by the differentiating.

12: A method for compressing digital data according to claim 11, wherein the extrapolation of the value of a sample of data to be compressed is a copy of the preceding sample.

13: A method for compressing digital data according to claim 11, further comprising conditioning each sample of data to be compressed to format the data to be compressed.

14: A method for compressing digital data according to claim 11, further comprising concatenating successive differentiated samples in which the redundancy has been deleted.

15: A method for decompressing digital data compressed by the method according to claim 11, comprising: re-introducing redundancy into the compressed signal, to produce reconstituted samples; de-differentiating between each reconstituted sample and a corresponding estimated sample, to produce a de-differentiated sample; estimating a value of each following estimated sample from a value of at least one previously produced de-differentiated sample.

16: A method for decompressing digital data according to claim 15, wherein estimating the value of a following estimated sample is carried out by a same function as for extrapolation during data compression.

17: A data compression device, comprising: means for extrapolating a value of each sample of data to be compressed as a function of a value of at least one preceding sample, to produce an extrapolated sample; means for differentiating between each extrapolated sample and the corresponding sample of data to be compressed, to produce a differentiated sample; means for deleting redundancy between successive differentiated samples produced by the means for differentiating.

18: A device for decompressing data compressed by the device according to claim 17, further comprising: means for re-introducing redundancy into the compressed signal, to produce reconstituted samples; means for de-differentiating between each reconstituted sample and a corresponding estimated sample, to produce a de-differentiated sample; means for estimating a value of each following estimated sample from a value of at least one previously produced de-differentiated sample.

19: A non-transitory computer readable medium storing a computer readable computer program comprising instructions for execution of the method according to claim 11 when the program is executed by a computer.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0041] Other characteristics and advantages will become clear on reading the following description of a preferred embodiment, given by way of non-limiting example, described with reference to the figures in which:

[0042] FIG. 1 represents a device for compressing digital data according to an embodiment of the invention,

[0043] FIG. 2 represents an embodiment of module for deleting redundancy implemented in the device of FIG. 1,

[0044] FIG. 3 represents a device for decompressing digital data according to an embodiment of the invention,

[0045] FIG. 4 represents a device for compressing digital data according to another embodiment of the invention,

[0046] FIG. 5 represents a device for decompressing digital data according to another embodiment of the invention,

[0047] FIG. 6 represents a method for compressing digital data according to an embodiment of the invention,

[0048] FIG. 7 represents a method for decompressing digital data according to an embodiment of the invention,

[0049] FIG. 8 represents a particular embodiment of implementation of data compression device according to the invention.

DETAILED DESCRIPTION OF PARTICULAR EMBODIMENTS

[0050] According to a preferred embodiment, represented in FIG. 1, the digital data compression device comprises a conditioning module 10 which receives the data to be compressed.

[0051] Samples of data which are octets are considered as an example in the remainder of the description. Obviously, it is possible to consider words of different size, strictly greater than 1 bit, for example 32 or 64 bits.

[0052] Conditioning is an optional operation of formatting data with the aim of facilitating the work of following modules and thus improving the performance of the device. The conditioning of data is for example the encoding of data according to a Gray code, which makes it possible to only modify a single bit at a time when a number is increased by one unit. It is also possible to change the endianness of the signal (big endian, little endian), or instead to modify the emplacement of the sign bit, in order to adapt the order of the bits to later processing operations.

[0053] An output of the conditioning module 10 is connected to an input of an extrapolation module 11. The conditioning module 10 receives samples of data to be compressed E.sub.n, and delivers samples of conditioned data to be compressed EC.sub.n to the extrapolation module 11. The integer n represents a current sample index, varying between 1 and a value N.

[0054] If the device does not comprise a conditioning module, the extrapolation module 11 receives the samples of data to be compressed E.sub.n and applies its processing operations to them.

[0055] The extrapolation module 11 applies to the samples that it receives an extrapolation function that produces an estimation of the value of the current sample.

[0056] Different extrapolation functions may be implemented. Preferably, the extrapolation function depends on the nature of the signal to be compressed.

[0057] As an example, the extrapolation function estimates the value of the current sample EC.sub.n as a function of the value of at least one preceding sample EC.sub.n-1, EC.sub.n-2, etc. In this case, the extrapolation function is for example a copy of the preceding sample. It may also be a function, linear or not, of several preceding samples. Alternatively, it may further be a parabolic or exponential function.

[0058] If the extrapolation function estimates the value of the current sample EC.sub.n as a function of the value of at least one preceding sample EC.sub.n-1, EC.sub.n-2, etc., this gives: EE.sub.n=f(EC.sub.n-1, EC.sub.n-2, . . . ), where EE.sub.n represents a current extrapolated sample. If the extrapolation function is a copy of the preceding sample, this gives: EE.sub.n=EC.sub.n-1.

[0059] An output of the extrapolation module 11 is connected to an input of a differentiating module 12. The extrapolation module 11 delivers the estimated, or extrapolated, samples EE.sub.n to the differentiating module 12.

[0060] Similarly, the output of the conditioning module 10 is connected to an input of the differentiating module 12. The conditioning module 10 delivers samples of conditioned data to be compressed EC.sub.n to the differentiating module 12.

[0061] If the device does not comprise a conditioning module, the differentiating module 12 receives the samples of data to be compressed E.sub.n.

[0062] The differentiation implements a deterministic function which associates a single value of differentiated sample ED.sub.n with a pair of values of conditioned sample and corresponding extrapolated sample (EC.sub.n, EE.sub.n).

[0063] The values of conditioned sample EC.sub.n and corresponding extrapolated sample EE.sub.n are a priori close, if the extrapolation works well. The differentiation function exploits the redundancy existing between the values of conditioned sample EC.sub.n and corresponding extrapolated sample EE.sub.n. For example, the extrapolation function is the function XOR applied bit by bit to the values of conditioned sample EC.sub.n and corresponding extrapolated sample EE.sub.c. In an alternative, the extrapolation function is an unsigned subtraction.

[0064] An output of the differentiating module 12 is connected to an input of a module for deleting redundancy 13. The differentiating module 12 delivers the differentiated samples ED.sub.n to the module for deleting redundancy 13.

[0065] FIG. 2 represents an embodiment of module for deleting redundancy 13 that works on blocks of P successive values of differentiated samples and determines the redundancy between said P values. For example, the result is the number NB of successive most significant bits which have as value 0 in each of the P differentiated samples considered. According to other implementations, it is also possible to consider the successive most significant bits which have as value 1 in each of the P differentiated samples considered, or instead the successive redundant least significant bits. The value P is predetermined, or in an alternative, it is variable and is encoded in the compression data.

[0066] The P successive values of differentiated samples are memorised then truncated from the NB successive redundant bits.

[0067] Finally, the P truncated values, that is to say the non-redundant parts of the P successive values of differentiated samples, are concatenated. The output signal of the module 13 is the signal of compressed data produced by the compression device according to the invention. The output signal of the module 13 comprises words of which each corresponds to P values processed and is formed from the number NB and the P truncated values.

[0068] FIG. 3 represents an embodiment of device for decompressing data compressed by the device of FIG. 1.

[0069] The decompression device comprises a de-concatenation module 20 which receives the compressed signal and carries out operations opposite to those of the module for deleting redundancy 13 described previously.

[0070] In the case of deleting redundancy realised as in the example described with reference to FIG. 2, the de-concatenation module 20 reads the number NB and the P truncated values of a received word. It adds the NB bits that had been truncated to each of the P values of the received word. For example, it adds NB most significant bits which have as value 0. The module 20 carries out a re-introduction of redundancy into the data that it receives and thereby reconstitutes the values of the differentiated samples. A reconstituted differentiated sample EDR.sub.n is identical to the corresponding sample produced by the differentiating module 12 of the data compression device. A reconstituted differentiated sample EDR.sub.n represents the error of the extrapolation function applied by the module 12 during data compression.

[0071] An output of the de-concatenation module 20 is connected to an input of a de-differentiating module 21. The de-concatenation module 20 delivers the reconstituted differentiated samples EDR.sub.n to the de-differentiating module 21.

[0072] An output of an estimation module 22 is connected to another input of the de-differentiating module 21. An output of the de-differentiating module 21 is connected to an input of the estimation module 22.

[0073] The estimation module 22 uses a function identical to that used by the extrapolation module 11 of the data compression device. From the previously de-differentiated samples EDD.sub.n supplied by the de-differentiating module 21, the estimation module 22 produces estimated samples EES.sub.n. For example, if the estimation function is a copy of the preceding sample, this then gives: EES.sub.n=EDD.sub.n-1, where EDD.sub.n-1 represents the previously de-differentiated sample.

[0074] These estimated samples EES.sub.n are supplied to the de-differentiating module 21 which applies a function opposite to the function applied by the differentiating module 12 of the data compression device. The de-differentiating module 21 produces a de-differentiated sample EDD.sub.n as a function of the estimated sample EES.sub.n and the corresponding reconstituted differentiated sample EDR.sub.n supplied by the module 20.

[0075] According to a preferred embodiment, the differentiating function is the function XOR. In this case, the function applied by the de-differentiating module 21 is also the function XOR.

[0076] The output of the de-differentiating module 21 is also connected to an input of a de-conditioning module 23. This module is optional and is implemented when the data compression device comprises a conditioning module 10.

[0077] The de-conditioning module 23 carries out operations opposite to those carried out by the conditioning module 10. For example, if the conditioning comprises the passage from a big endian type encoding to a little endian type encoding, then the de-conditioning realises the opposite transformation.

[0078] The output signal of the module 23 is the signal of decompressed data produced by the decompression device according to the invention. Obviously, if the conditioning/de-conditioning operations are not implemented, then it is the output signal of the module 21 which is the signal of decompressed data produced by the decompression device according to the invention.

[0079] FIG. 4 represents another embodiment of data compression device according to the invention.

[0080] Compared to the embodiment of FIG. 1, the optional conditioning module is displaced. More precisely, the data compression device comprises an extrapolation module 11, a differentiating module 12 and a module for deleting redundancy 13 which are analogous to those described previously and which are designated respectively by the same numerical references.

[0081] The data compression device comprises a first conditioning module 10.sub.1 between the output of the extrapolation module 11 and the first input of the differentiating module 12 and a second conditioning module 10.sub.2 connected to the second input of the differentiating module 12.

[0082] The conditioning of the data thus takes place just before the differentiation between the data to be compressed and the extrapolated data.

[0083] FIG. 5 represents another embodiment of data decompression device according to the invention, corresponding to the compression device of FIG. 4.

[0084] Compared to the embodiment of FIG. 3, the optional de-conditioning module is displaced. More precisely, the data decompression device comprises a de-concatenation module 20, a de-differentiating module 21 and an estimation module 22 which are analogous to those described previously and which are designated respectively by the same numerical references.

[0085] The de-concatenation 20 and de-differentiating 21 modules work on data that are conditioned. The data decompression device comprises a de-conditioning module 23 between the output of the de-differentiating module 21 and the output of the device. The estimation module 22 has an input connected to the output of the de-conditioning module 23. Thus, the estimation module 22 works on data that are not conditioned, like the extrapolation module 11 of the data compression device.

[0086] A conditioning module 24 is connected between an output of the estimation module 22 and an input of the de-differentiating module 21. Thus, the two inputs of the de-differentiating module 21 receive data that are conditioned. The conditioning carried out by the module 24 is identical to that carried out by the modules 10.sub.1 and 10.sub.2 of the data compression device described with reference to FIG. 4.

[0087] FIG. 6 represents the operation of the data compression device of FIG. 1, in the form of a flow diagram comprising the steps E10 to E13.

[0088] Step E10 is a conditioning of the samples of data to be compressed E.sub.n. This conditioning is optional. The conditioning of the data is a formatting of the data with the aim of facilitating the compression thereof.

[0089] The step of conditioning E10 produces samples of conditioned data to be compressed EC.sub.n.

[0090] The following step E11 is an extrapolation realised on the conditioned samples EC.sub.n. If conditioning is not carried out, extrapolation is carried out on the samples of data to be compressed E.sub.n. Similarly, the later processing operations carried out on the conditioned samples are carried out on the samples of data to be compressed.

[0091] Different extrapolation functions may be implemented. Preferably, the extrapolation function depends on the nature of the signal to be compressed.

[0092] As an example, the extrapolation function estimates the value of the current sample EC.sub.n as a function of the value of at least one preceding sample EC.sub.n-1, EC.sub.n-2, etc. In this case, the extrapolation function is for example a copy of the preceding sample.

[0093] It may also be a function, linear or not, of several preceding samples. Alternatively, it may further be a parabolic or exponential function.

[0094] The following step E12 is a differentiation carried out on each pair of conditioned sample and corresponding extrapolated sample (EC.sub.n, EE.sub.n). The differentiation implements a deterministic function which associates a single value of differentiated sample ED.sub.n with a pair of values of sample and corresponding extrapolated sample (EC.sub.n, EE.sub.n).

[0095] The values of conditioned sample EC.sub.n and corresponding extrapolated sample EE.sub.n are a priori close, if the extrapolation works well. The differentiating function exploits the redundancy existing between the values of conditioned sample EC.sub.n and corresponding extrapolated sample EE.sub.n. For example, the extrapolation function is the function XOR applied bit by bit to the values of conditioned sample EC.sub.n and corresponding extrapolated sample EE.sub.n. In an alternative, the extrapolation function is an unsigned subtraction.

[0096] The following step E13 is a deletion of redundancy in the differentiated samples ED.sub.n. As an example, the deletion of redundancy is carried out as described with reference to FIG. 2.

[0097] In this case, the deletion of redundancy considers blocks of P successive values of differentiated samples and determines the redundancy between said P values.

[0098] For example, the result is the number NB of successive most significant bits which have as value 0. The value P is predetermined, or in an alternative, it is variable and is encoded in the compression data.

[0099] The P successive values of differentiated samples are memorised then truncated from the NB successive redundant bits.

[0100] Finally, the P truncated values are concatenated. The result of step E13 is the signal of compressed data. This signal comprises words of which each corresponds to P processed values and is formed from the number NB and the P truncated values.

[0101] FIG. 7 represents the operation of the data decompression device of FIG. 3, in the form of a flow diagram comprising the steps E20 to E23.

[0102] Step E20 is a de-concatenation which carries out operations opposite to those of the step of deleting redundancy E13 described previously. This step comprises an actual de-concatenation of the compressed signal and a re-introduction of redundancy in the compressed signal.

[0103] In the case of a deletion of redundancy realised as in the example described with reference to FIG. 2, the number NB and the P truncated values of a received word are read. The NB bits that had been truncated are added to each of the P values of the received word. For example, NB most significant bits that have as value 0 are added to the truncated values. The values of the differentiated samples which represent the error of the extrapolation function applied by step E11 during data compression are thereby reconstituted. Step E20 has for result values of reconstituted differentiated samples EDR.sub.n.

[0104] The following step E21 is a de-differentiation which applies to the reconstituted differentiated samples EDR.sub.n a function opposite to the function applied by the differentiating step E12 of the data compression method.

[0105] Step E21 produces a current de-differentiated sample EDD.sub.n as a function of the corresponding reconstituted differentiated sample EDR.sub.n resulting from step E20 and from a corresponding estimated sample EES.sub.n resulting from step E22 described hereafter.

[0106] The following step E22 is an estimation which uses a function identical to that used by the extrapolation step E11 of the data compression method. From the previously de-differentiated samples EDD.sub.n supplied by the de-differentiating step E21, the estimation step E22 produces estimated samples EES.sub.n. For example, the estimation is a copy of the preceding sample: EES.sub.n=EDD.sub.n-1, where EDD.sub.n-1 represents the previously de-differentiated sample.

[0107] These estimated samples EES.sub.n are used by the de-differentiating step E21 which applies a function opposite to the function applied by the differentiating step E12 of the data compression method. According to a preferred embodiment, the differentiating function is the function XOR. In this case, the function applied by the de-differentiating module 21 is also the function XOR.

[0108] Step E21 is also followed by step E23 of de-conditioning the de-differentiated samples EDD.sub.n produced at step E21. This step is optional and is implemented when the data compression method comprises a conditioning step E10.

[0109] The de-conditioning step E23 carries out operations opposite to those carried out by the conditioning step E10. For example, if the conditioning comprises the passage from a big endian type encoding to a little endian type encoding, then the de-conditioning realises the opposite transformation.

[0110] The signal produced at step E23 is the signal of decompressed data produced by the decompression method according to the invention. Obviously, if the conditioning/de-conditioning operations are not implemented, then it is the signal produced at step E21 which is the signal of decompressed data produced by the decompression method according to the invention.

[0111] According to another embodiment, the steps of conditioning and de-conditioning of the methods for compressing and decompressing data may be implemented respectively after the extrapolation and after the de-differentiation, by adding a step of conditioning between the estimation and the de-differentiation in the method for decompressing data.

[0112] The methods for compressing and decompressing data according to the invention may be implemented by one or more dedicated integrated circuit(s) or by programmable processors, or instead in the form of computer programmes memorised in the memory of a computer.

[0113] Thus, FIG. 8 represents a particular embodiment of implementation of the compression of data according to the invention.

[0114] The data compression device has the general structure of a computer. It notably comprises a processor 100 executing a computer programme implementing the method according to the invention, a memory 101, an input interface 102 and an output interface 103.

[0115] These different elements are conventionally connected by a bus 105.

[0116] The input interface 102 is intended to receive the data to be compressed.

[0117] The processor 100 executes the processing operations described previously. These processing operations are conducted in the form of code instructions of the computer programme which are memorised by the memory 101 before being executed by the processor 100.

[0118] The memory 101 may further memorise the results of the processing operations carried out.

[0119] The output interface 103 supplies the compressed data which may next be memorised and/or transmitted in a conventional manner.

[0120] Obviously, the method and the corresponding data decompression device are implemented in a similar manner. A same device can also implement the compression and the decompression of data.