Method for coding by random acoustic signals and associated transmission method

Abstract

The invention relates to a method for coding information symbols of an alphabet into random acoustic signals. The coding dictionary is constructed in a heuristic manner by acquiring a set of random signals, by filtering same by way of the equivalent filter of the transmission channel, by selecting subsets of these signals, and, for each subset, by calculating the correlation matrix of the selected signals, the coding dictionary being constituted by the subset for which the correlation matrix most closely resembles a diagonal matrix. The invention also relates to a method for transmitting and receiving information symbols by way of acoustic signals.

Claims

1. Method for coding information symbols belonging to an alphabet by means of acoustic signals, wherein: (a) a set of random signals is acquired and they are filtered by a filter of interest having for response the response of the transmission channel on which these signals are intended to be transmitted; (b) sub-sets of N random signals thereby filtered of said set are selected and, for each sub-set, a correlation matrix of the signals thereby selected is calculated; (c) the sub-set of N signals corresponding to the correlation matrix the closest to a diagonal matrix is retained as coding dictionary; (d) each information symbol of the alphabet is coded by a random signal of the dictionary, said random signal of the dictionary being transformed into an acoustic signal by a transducer.

2. Method for coding according to claim 1, wherein said random signals are acquired by a random generator using thermal noise or ground noise.

3. Method for coding according to claim 1, wherein at step (c): (c1) a new random signal belonging to said set is successively substituted by one of the random signals of a first selected sub-set of signals; (c2) the correlation matrix of the random signals is calculated for each of the sub-sets thereby substituted and a quality factor characterising the proximity of the correlation matrix to a diagonal matrix is deduced therefrom; the steps (c1) and (c2) being repeated as long as the random signals of said set have not been exhausted and/or the quality factor is below a predetermined threshold value.

4. Method for coding according to claim 1, wherein, prior to step (b), from each random signal is subtracted its average so that said random signals are centred.

5. Method for coding according to claim 4, wherein the quality factor is calculated with a formula $Q^{\prime }=\frac{\underset{i}{\min }\left(.Math.C_{\mathrm{ii}}^{\prime }.Math.\right)}{\underset{\underset{i\ne j}{i,j}}{\min }\left(.Math.C_{\mathrm{ij}}^{\prime }.Math.\right)}\mathrm{or}{Q}^{\prime }=\underset{i}{\min }\left(\frac{.Math.C_{\mathrm{ii}}^{\prime }.Math.}{\underset{j\ne i}{\max }\left(.Math.C_{\mathrm{ij}}^{\prime }.Math.\right)}\right)$ or instead $Q^{\prime }=\frac{\underset{i}{\mathrm{moy}}\left(.Math.C_{\mathrm{ii}}^{\prime }.Math.\right)}{\underset{\underset{i\ne j}{i,j}}{\mathrm{moy}}\left(.Math.C_{\mathrm{ij}}^{\prime }.Math.\right)}$ where the coefficients C′.sub.ij are the elements of the correlation matrix and where min, max and moy signify respectively the minimum value, the maximum value and the average value.

6. Method for coding according to claim 4, wherein, prior to step (b), the energy of the centred random signals is normalized so as to obtain normalized random signals all having a same average energy per sample.

7. Method for coding according to claim 6, wherein the quality factor is calculated with a formula $Q=\frac{E_0}{\underset{\underset{i\ne j}{i,j}}{\max }\left(.Math.C_{\mathrm{ij}}.Math.\right)}\mathrm{or}Q=\frac{E_0}{\underset{\underset{i\ne j}{i,j}}{\mathrm{moy}}\left(.Math.C_{\mathrm{ij}}.Math.\right)}$ or instead $Q=\frac{E_0}{\underset{\underset{i\ne j}{i,j}}{.Math.}.Math.C_{\mathrm{ij}}.Math.}$ where the coefficients C.sub.ij are the elements of the correlation matrix and E.sub.0 is said average energy per sample of the random signals and where min, max and moy signify respectively the minimum value, the maximum value and the average value.

8. Method for transmitting information symbols belonging to an alphabet by acoustic signals, wherein said symbols are coded by the method for coding by acoustic signals according to claim 1, the acoustic signals corresponding to successive information symbols being transmitted sequentially on the transmission channel.

9. Method for transmitting information symbols belonging to an alphabet by acoustic signals, wherein said symbols are coded by the method for coding according to claim 1, a plurality of acoustic signals corresponding to different information symbols being transmitted simultaneously on the transmission channel.

10. Method for transmitting information symbols according to claim 8, wherein a channel coding of blocks of said symbols is carried out prior to their coding by acoustic signals.

11. Method for receiving information symbols transmitted by the method for transmitting of claim 8, wherein the acoustic signal received during a symbol time is transformed into an electrical signal by a transducer, then correlated with each of the random signals of the coding dictionary to provide a plurality of correlation results, the highest correlation result in absolute value providing the index of a symbol received during said symbol time.

12. Method for receiving information symbols transmitted by the method for transmitting of claim 9, wherein the acoustic signal received during a symbol time is transformed into an electrical signal by a transducer, then correlated with each of the random signals of the coding dictionary to provide a plurality of correlation results, the correlation results above, in absolute value, a predetermined threshold value providing the indices of the symbols received during said symbol time.

13. Method for receiving information symbols transmitted by the method for transmitting of claim 10, wherein the acoustic signal received during a symbol time is transformed into an electrical signal by a transducer, then correlated with each of the random signals of the coding dictionary to provide a plurality of correlation results, the correlation results above, in absolute value, a predetermined threshold value providing the indices of the symbols received during said symbol time, the blocks of symbols received next being subjected to a channel decoding.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other characteristics and advantages of the invention will become clear from reading preferential embodiments of the invention made with reference to the appended figures, among which:

(2) FIG. 1 schematically represents a method for constructing a coding dictionary by means of random acoustic signals according to a first embodiment of the invention;

(3) FIG. 2 schematically represents a method for constructing a coding dictionary by means of random acoustic signals according to a second embodiment of the invention;

(4) FIG. 3 represents an autocorrelation matrix of the random acoustic signals used in the coding of FIG. 2;

(5) FIG. 4 schematically represents a method for transmitting information symbols coded by means of random acoustic signals, according to an embodiment of the invention;

(6) FIG. 5 schematically represents a method for receiving a random acoustic signal transmitted by the transmission method of FIG. 4.

DETAILED DESCRIPTION OF PARTICULAR EMBODIMENTS

(7) A system for transmitting/receiving on an acoustic channel will be considered hereafter. Acoustic channel is taken to mean a channel for propagating a sonic wave (in the domain of audible frequencies 20 Hz-20 kHz), or even an ultrasonic wave (that is to say of frequency greater than 20 kHz) or an infrasonic wave (that is to say of frequency less than 20 Hz).

(8) The message to code, and if need be to transmit, is constituted of information symbols belonging to a predetermined alphabet. This alphabet is constituted for example of a set of words of n bits, where n>1. Generally speaking, for an alphabet A of cardinal N, it is always possible to come down to a set of binary words of size n=┌log.sub.2(N)┐.

(9) The basic idea of the invention is to construct in a heuristic manner a coding of the symbols of the alphabet A by random acoustic signals. More specifically, in assuming that a set S of cardinal M>>N of random signals is generated, the basic idea of the invention is to select a sub-set S.sub.A⊂S of these M random signals, respecting a certain quality criterion, and to associate in a one-to-one manner with each symbol of the alphabet A one of the random signals thereby selected. The injection of A into S thereby obtained then defines a coding by random signals which are next reproduced by an electroacoustic transducer, hence the qualification of random acoustic coding.

(10) FIG. 1 schematically represents a method for constructing a coding dictionary by means of random acoustic signals, according to a first embodiment of the invention.

(11) According to a first alternative, the construction of the coding dictionary (or codebook) is carried out in a sequential manner, by successive iterations. Alternatively, the construction of the coding dictionary could be carried out in a parallel manner as explained hereafter.

(12) At step 110, a set of random acoustic signals is acquired. These signals have been obtained for example by means of a random generator using a physical phenomenon such as thermal noise at the terminals of a resistance or the ground noise of a microphone. These signals are acquired by means of an acquisition chain having a predetermined passband then sampled at the corresponding Nyquist frequency. Alternatively, the random signals may have been obtained by a pseudo-random generator, advantageously chosen of cryptographic quality. Hereafter, it is explicitly understood that the expression “random signals” covers these two alternatives. Whatever the case, each random signal is thereby constituted of L samples, and stored in a memory.

(13) At step 120, the random signals are optionally filtered with a filter having a size of interest, for example a filter having for response the response of the transmission channel. The response of the transmission channel is constituted by the convolution of the response of the amplification chain, the response of the transmission transducer (loudspeaker, piezoelectric transducer or other), the response of the propagation channel, the response of the reception transducer (microphone, piezoelectric transducer or other) and finally the response of the reception chain.

(14) At step 130, each of the random signals is centred and normalized, if need be filtered at step 120, so as to obtain a set S of centred random acoustic signals of same energy E. More specifically, if s.sub.i=(s.sub.i(1), . . . s.sub.i(L)) denotes a random acoustic signal generated previously, the corresponding centralised and normalized signal is given by s.sub.i (s.sub.i(1), . . . s.sub.i(L)) with:

(15) $\begin{array}{cc}{\stackrel{\_}{s}}_i\left(\ell \right)=\frac{\sqrt{E_0}}{\sqrt{\underset{\ell =1}{\overset{L}{.Math.}}{\left(s_i\left(\ell \right)-\mu s_i\right)}^2}}\left(s_i\left(\ell \right)-\mu s_i\right)& \left(1\right)\end{array}$
where

(16) $\mu s_i=\frac{1}{L}\underset{\ell =1}{\overset{L}{.Math.}}{s}_i\left(\ell \right)$
is the average of the signal s.sub.i and E.sub.0=E/L is the average energy per sample of the random signals.

(17) At step 140, a sub-set S.sub.N of S is arbitrarily selected constituted of N centred and normalized random signals s.sub.i, i=1, . . . , N and the correlation matrix of these signals is calculated. The correlation matrix is a symmetrical matrix of size N×N of which the elements are the correlation coefficients:

(18) $\begin{array}{cc}{C}_{\mathrm{ij}}=\underset{\ell =1}{\overset{L}{.Math.}}{\stackrel{\_}{s}}_i\left(\ell \right){\stackrel{\_}{s}}_j\left(\ell \right)& \left(2\right)\end{array}$
and of which the diagonal elements are all equal to E.sub.0.

(19) Hereafter, the quality factor of the correlation matrix, or in an equivalent manner the quality factor of the set S.sub.N, will be called the value:

(20) $\begin{array}{cc}Q=\frac{E_0}{\underset{\underset{i\ne j}{i,j}}{\max }\left(.Math.C_{\mathrm{ij}}.Math.\right)}& \left(3\right)\end{array}$
or, alternatively:

(21) $\begin{array}{cc}Q=\frac{E_0}{\underset{\underset{i\ne j}{i,j}}{\mathrm{moy}}\left(.Math.C_{\mathrm{ij}}.Math.\right)}& \left(4\right)\end{array}$
where

(22) 0$\underset{\underset{i\ne j}{i,j}}{\mathrm{moy}}\left(.Math.C_{\mathrm{ij}}.Math.\right)=\frac{2}{N\left(N-1\right)}\underset{\underset{i<j}{i,j=1,\mathrm{.Math.},N}}{.Math.}.Math.C_{\mathrm{ij}}.Math.$
is the average of the absolute values of the out-of-diagonal elements of the correlation matrix (taking into account that the matrix is symmetrical).

(23) Again alternatively, the quality factor may be defined by:

(24) $\begin{array}{cc}Q=\frac{E_0}{\underset{\underset{i\ne j}{i,j}}{.Math.}.Math.C_{\mathrm{ij}}.Math.}& \left(5\right)\end{array}$

(25) Generally speaking, the correlation matrix C is characterised by a quality factor Q translating its proximity to a diagonal matrix, the quality factor being all the higher when the non-diagonal elements of the matrix are lower compared to the diagonal elements.

(26) An iterative loop is next entered into at 150.

(27) At step 150, a new centred and normalized random signal s.sub.k of S.sub.i not yet considered, is taken into account, consequently s.sub.k.Math.S.sub.N.

(28) At step 160, the correlation matrices C.sub.i.fwdarw.k, i=1, . . . , N, of size N×N, of the random signals s.sub.l, . . . , s.sub.i−l, s.sub.k, s.sub.i+l, . . . , s.sub.N are calculated. In other words, each of the N signals of S.sub.N is successively substituted by the signal s.sub.k and each time the correlation matrix of the signals is calculated after this substitution.

(29) It will be noted that the calculation of the matrix C.sub.i.fwdarw.k only requires the calculation of N−1 correlation coefficients according to the expression (2) namely the signal s.sub.k with the signals s.sub.l, . . . , s.sub.i−l, s.sub.i+l, . . . , s.sub.N, the other coefficients having been calculated previously.

(30) The quality factor Q.sub.i.fwdarw.k for each of the matrices C.sub.i.fwdarw.k, i=1, . . . , N is next determined, according to one of the expressions (3) to (5) and the following is deduced therefrom:

(31) $\begin{array}{cc}{Q}_k^{\max }=\underset{i=1,\mathrm{.Math.},N}{\max }\left(Q_{i->k}\right)& \left(6\right)\end{array}$

(32) At 170, a test is done to determine if Q.sub.k.sup.max is above the value Q, in other words if a substitutions s.sub.i by s.sub.k exists making it possible to improve the quality factor of the set S.sub.N. If not, one passes to step 185 to test a stop criterion. If so, one passes to step 180.

(33) At step 180, in the set S.sub.N, the signal s.sub.h with h=arg max (Q.sub.i.fwdarw.k) is substituted by the signal s.sub.k and the quality factor is updated: Q=Q.sub.k.sup.max.

(34) At step 185, a stop criterion is tested. If the stop criterion is satisfactory, the construction of the code ends at 190. Failing this, a new random acoustic signal is taken into account at 150.

(35) A first stop criterion may be the exhaustion of the set S.

(36) Alternatively or cumulatively, a second stop criterion may be obtaining a quality factor above a predetermined threshold value Q.sub.Th.

(37) The loop 150-185 is repeated as long as the signals of S (first stop criterion) have not been exhausted or a quality factor above the threshold value (second stop criterion) obtained.

(38) Thus, a set S.sub.N of random acoustic signals having a low level of correlation with each other is progressively constructed.

(39) Instead of proceeding in an iterative manner, it is possible to proceed in a parallel manner. In this case, all the possible combinations of N random signals of S are at once considered and the quality factor of their correlation matrix is calculated for each of these combinations. Finally the combination leading to the highest quality factor is selected. The resulting set S.sub.N of random signals constitutes the coding dictionary.

(40) FIG. 2 schematically represents a method for constructing a coding dictionary by means of random acoustic signals according to a second embodiment of the invention.

(41) The steps 210 and 220 of acquisition and filtering of a set of random signals are identical to steps 110 and 120 of FIG. 1 and will thus not be described again.

(42) At step 230, from each signal is subtracted its average so as to obtain a set of centred random signals, s.sub.i. However, unlike the first embodiment, the random signals are not here energy normalized. Optionally, the signals of energy below a predetermined threshold E.sub.Th could however be eliminated. A set S of random signals is eventually obtained.

(43) At step 240, a sub-set S.sub.N of S constituted of N centred random signals s.sub.i, i=1, . . . , N is arbitrarily selected and the correlation matrix of these signals is calculated. The elements of this correlation matrix are given by:

(44) $\begin{array}{cc}{C}_{\mathrm{ij}}^{\prime }=\underset{\ell =1}{\overset{L}{.Math.}}{\tilde{s}}_i\left(\ell \right){\tilde{s}}_j\left(\ell \right)& \left(7\right)\end{array}$

(45) Unlike the first embodiment, the elements of the diagonal are not identical. The quality factor of the correlation matrix is next calculated, that is to say, in an equivalent manner, the quality factor of the set S.sub.N.

(46) In this embodiment, the quality factor may be calculated as follows:

(47) $\begin{array}{cc}{Q}^{\prime }=\frac{\underset{i}{\min }\left(.Math.C_{\mathrm{ii}}^{\prime }.Math.\right)}{\underset{\underset{i\ne j}{i,j}}{\min }\left(.Math.C_{\mathrm{ij}}^{\prime }.Math.\right)}& \left(8\right)\end{array}$
or, alternatively:

(48) $\begin{array}{cc}{Q}^{\prime }=\underset{i}{\min }\left(\frac{.Math.C_{\mathrm{ii}}^{\prime }.Math.}{\underset{j\ne i}{\max }\left(.Math.C_{\mathrm{ij}}^{\prime }.Math.\right)}\right)& \left(9\right)\end{array}$
or even:

(49) $\begin{array}{cc}{Q}^{\prime }=\frac{\underset{i}{\mathrm{moy}}\left(.Math.C_{\mathrm{ii}}^{\prime }.Math.\right)}{\underset{\underset{i\ne j}{i,j}}{\mathrm{moy}}\left(.Math.C_{\mathrm{ij}}^{\prime }.Math.\right)}& \left(10\right)\end{array}$

(50) As in the first embodiment, the quality factor Q′ reflects the proximity of the correlation matrix to a diagonal matrix.

(51) An iterative loop is next entered into, the steps 250 to 285 being identical to the steps 150 to 185 described previously with the sole difference that the quality factor, Q′, is calculated using one of the expressions (7) to (9).

(52) When the stop criterion is met, that is to say when the set S is exhausted or when, by successive substitutions, a sub-set S.sub.N has been found of which the quality factor is below a predetermined threshold value Q′.sub.Th, the resulting sub-set S.sub.N is the sought after coding dictionary.

(53) FIG. 3 represents the elements of a correlation matrix of random acoustic signals of a coding dictionary constructed according to the method of FIG. 2. More specifically, the absolute values |C′.sub.ij| of the correlation coefficients of the random acoustic signals of the dictionary S.sub.N are here represented, with N=256. It may be observed that the correlation coefficients of the main diagonal, that is to say the energies of the different random signals, are substantially higher than the out-of-diagonal correlation coefficients.

(54) FIG. 4 schematically represents a method for transmitting information symbols by means of random acoustic signals, according to an embodiment of the invention.

(55) It is assumed that a coding dictionary according to the method of FIG. 1 or FIG. 2 has been generated beforehand, in other words that a set S.sub.N of random acoustic signals is available.

(56) The words to transmit are optionally coded at 410 by means of a channel coding, for example a BCH or Reed-Solomon type block coding. If need be, a CRC code could also be added thereto, in a manner known per se. The blocks thereby coded by the channel coding and/or CRC coding are next divided into words of size.sub.n and consequently symbols of an alphabet A of cardinal N=2.sup.n.

(57) At each word of n bits, x.sub.1.sup.i . . . x.sub.n.sup.j, the random signal of S.sub.N that is associated therewith in a one-to-one manner is read at 420 in the memory 430. This signal is next converted into an analogue signal at 440 then amplified at 450 before being transmitted by a transducer at 460 (loud speaker or piezoelectric transducer for example).

(58) Thus, a sequence of words to transmit is transformed into an acoustic signal constituted by a sequence of random acoustic signals of S.sub.N.

(59) Alternatively, several words, i.e. several symbols of the alphabet A, could be transmitted simultaneously on the transmission channel. In this case, the acoustic signal transmitted during a word period will be simply constituted by the sum of the random acoustic signals associated with these different words.

(60) FIG. 5 schematically represents a method for receiving an acoustic signal transmitted by the method for transmitting of FIG. 4.

(61) The acoustic signal received by the transducer 510 is converted into an electrical signal which, if need be, is amplified (step not represented) then sampled at 520 at the Nyquist frequency. The sequence of samples thereby obtained is correlated in a battery of correlators in parallel 530.sub.1, . . . , 530.sub.N with the base random signals s.sub.i, i=1, . . . , N (or {tilde over (s)}.sub.i, i=1, . . . , N in the second embodiment) of the dictionary S.sub.N.

(62) The correlators may be realised for example in the form of filters matched to the base random signals s.sub.i, i=1, . . . , N (or {tilde over (s)}.sub.i i=1, . . . , N in the second embodiment).

(63) It will firstly be assumed that the transmission takes place in a sequential manner and that the correlators are synchronised with the transitions between successive words. It could notably be provided to transmit a pilot sequence as a preamble (for example a frame header) as a preamble of the payload, enabling the correlators to become synchronised with the word rhythm 1/T.

(64) The correlation results at the output of the different correlators are compared with each other at 540, at the end of each period T. The index i of the signal s.sub.i ({tilde over (s)}.sub.i) corresponding to the highest correlation result in absolute value gives the index of the symbol of the alphabet A that has been transmitted. In practice, the index i is used at 550 as address element to read a memory 560 in which the words x.sub.1.sup.j . . . x.sub.n.sup.j of the alphabet A are stored.

(65) The word of n bits read at this address, {circumflex over (x)}.sub.1.sup.j . . . {circumflex over (x)}.sub.n.sup.i, is supplied to a channel decoder 570. The channel decoder concatenates the consecutive words to form blocks and carries out a channel decoding of these blocks. Those skilled in the art will understand that the channel decoding will make it possible to correct certain errors that are able to affect the transmitted blocks and that the calculation of the CRC will make it possible to determine if these blocks have been correctly decoded.

(66) According to an alternative, several words may be transmitted simultaneously on the transmission channel. In this case, the correlation results are not compared with each other (in absolute value) but with a predetermined threshold value. The outputs of the correlators then give the indices of the words of the alphabet A that have been transmitted. In the same way, after concatenation of the words into blocks, a channel decoding of the blocks may next be carried out.

(67) Numerous other alternatives could be envisaged by those skilled in the art without going beyond the scope of the present invention. For example, at the level of the transmission, it could be possible to provide that the random signals are used to modulate a carrier or a plurality of sub-carriers before the amplification step. In a symmetrical manner, the signal received by the acoustic transducer could undergo a corresponding demodulation before being correlated by the battery of correlators.

(68) Due to the random nature of the acoustic signals, it is difficult for a third party listening to the channel to decode them to obtain the transmitted information symbols. Moreover, a plurality of sets S.sub.N could be provided at the transmission side and at the reception side, these sets being used according to a predetermined sequence. Alternatively, the switching from one set S.sub.N to another could be commanded by a control word transmitted on the acoustic channel or instead on an auxiliary channel.