158
pp. 158-177
La quantification vectorielle des signaux : approche alg6brique *
Jean-Pierre ADOUL
**
Analyse
La quantification vectorielle sph6rique (QVS) consiste quantifier s@ardment la norme d'un vecteur d'une part et son o r i e n t a t i o n d'autre part. La raise en wuvre d'un tel quantificateur ndcessite la specification d'un ensemble de vecteurs normds (points sur la sphere unitd) qui sont les valeurs arrondies possibles pour l"orientation du vecteur. Une far efficace de construire un quantificateur consiste ~ consid~rer le sous-ensemble sph6rique d'un r6seau r6gulier de points. En particulier un algorithme tr~s rapide est donn~ pour la Qvs utilisant les points du r~seau de Gosset en 8 dimensions. Un second algorithme (optimal dgalement) est donnd pour le r6seau de Leech en 24 dimensions. Les performances de tels quantificateurs pour le bruit blanc gaussien sont compar6es aux limites pr~dites par la th~orie de l'information. Enfin l'application de ces techniques au codage du rdsidu de parole est discutde. Mots cl6s : Quantification signal, Quantification bloc, Coordonn~e sph~rique, M~thode alg6brique, Code correcteur erreur, Code lin6aire, Codage pr6dictif, Traitement parole, Th6orie information.
SIGNAL VECTOR ALGEBRAIC
QUANTIZATION APPROACH
:
optimal, & given for the Leech lattice in 24 dimensions. The performances of such quantizers for white Gaussian noise is compared to information theory limits. Finally, the application of these techniques for encoding speech residual is discussed. Key words : Signal quantizing, Bloc quantizing, Spherical coordinate, Algebraic. . method, Error correctin,g code,. Linear code, Predmtwe coding, Speech processing, Information theory.
Sommaire
I.
Prdliminaires. II. Principe de la quantification vectorielle. III. Comparaison entre quantificateurs scalaires et vectoriels. IV. Quantification vectorielle sphdrique. V. Rdseaux rdguliers de points. VI. Quantification vectorielle sphdrique t~ partir de rdseaux. VII. Performances de la quantification vectorielle sphdrique par rdseau sur le bruit gaussien. V I I I . Application gtla transmission de parole d bas ddbit. IX. Conclusion. Bibliographie (39 rdf ).
Abstract
Spherical vector quantization (SVQ) cons&ts of quantizing separately on the one hand the norm of a vector and, on the other hand, its o r i e n t a t i o n . Implementing such quantizer requires a set of normalized vectors (points on the unit sphere) which are the possible rounded-off values for the vector's orientation. A clever way to design such a quantizer consists of taking a spherical subset from a regular point lattice. In particular a fast algorithm is given for the Gosset lattice in 8 dimensions..4 second algorithm, equally
I.
PRI~LIMINAIRES
L a q u a n t i f i c a t i o n est l ' o p 6 r a t i o n de d i s c r ~ t i s a t i o n d ' u n e o u p l u s i e u r s v a r i a b l e s . P o u r une seule v a r i a b l e , le p r o c e s s u s est b i e n c o n n u . L a figure 1 illustre la c a r a c t 6 r i s t i q u e en m a r c h e d ' e s c a l i e r d ' u n tel q u a n t i f i c a t e u r que l ' o n a p p e l l e r a scalaire. Le q u a n t i f i c a t e u r f a i t c o r r e s p o n d r e ~ l a v a r i a b l e d ' e n t r 6 e x u n e v a l e u r a p p r o c h 6 e Yi choisie d a n s u n
* Etude r6alis6e durant un s6jour sabbatique h I'ENST, Paris. ** Au Centre de recherche sur les communications, Universit6 de Sherbrooke, Sherbrooke, Qu6bec, Canada, JIK 2RI.
ANN. T~LI~COMMUN.,41, n ~ 3-4, 1986
1/20
159
J.-P. ADOUL. -- LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
Q(x)
r
o--V- l r
L 9" ! |
FIG. 2 . Le quantificateur fournit une m~me information (2-1) s o u s d e u x f o r m e s d i s t i n c t e s (2-2). P a r f o i s o n o b t i e n t d ' a b o r d la v a l e u r a r r o n d i e p u i s vient le c o d a g e (2-3). C ' e s t le p o i n t d e v u e a d p o t 6 e n DPCM O/a Y r e t o u r n e h la b o u c l e de r 6 t r o a c t i o n t a n d i s q u e << i>> est t r a n s m i s . P a r f o i s e n c o r e , c o m m e clans le c a s d ' u n c o n v e r t i s s e u r a n a l o g i q u e n u m 6 r i q u e , c ' e s t l ' i n d i c e i q u i est f o u r n i d ' e m b l 6 e (2-4) ; la v a l e u r a r r o n d i e s ' o b t e n a n t p a r la table de d 6 c o d a g e ( l ' e n s e m b l e S).
tj2
.~
FIG. 1. ~ C a r a e t 6 r i s t i q u e t y p i q u e d ' u n q u a n t i f i c a t e u r scalaire de N = 6 n i v e a u x . A titre d ' e x e m p l e s i x se t r o u v e e n t r e les seuils Ss et S a i l est a r r o n d i /~ la v a l e u r Y~. O n s ' a t t e n d h c e q u e le v e c t e u r d ' e n t r 6 e x, se t r o u v e e n t r e - - S c et + S e . D a n s le c a s c o n t r a i r e o n a u n effet de s a t u r a t i o n .
Typical scalar quuntizer characteristic for N = 6 levels. For examplea i f x lies between thresholds Sz and S~ it is rounded o f f at Yn. The input x is expected to lie within - - Sr and + Sr I f it is not the case there is an overload error.
The quantizer supplies one information (2-1) under two forms (2-2). In some instances the rounded-off value is obtained first (2-3). This is the viewpoint o f DPCM where y is f e d back to the predictor while index ~ i ~ is transmitted. Sometime, as in the case o f a analog-digital conversion, the index is obtained readily (2-4) ; the rounded-off value being read from the decoding table ( S ) .
p o u r lequel la table donne la meilleure a p p r o x i m a t i o n (ou erreur de quantification) que l ' o n d6finira bient6t. ensemble fini de N valeurs pr6d6termin6es. Soit S 1'ensemble ordonn6 des N valeurs arrondies disponibles : (1)
S -----{y,]i ---- 0, 1, 2 . . . . . N - -
II. PRINCIPE DE LA QUANTIFICATION VECTORIELLE
1}.
On peut alors 6crire la fonction de quantification sous la f o r m e : (2)
y~ = Q(x) ; oh i appartient h [0, 1, 2 ..... N - - 1].
U n quantificateur fournit une seule information de sortie mais celle-ci est disponible sous deux formes ( y e t i). La figure 2 donne quatre diagrammes blocs 6quivalents qui mettent en relief la distinction. P a r la suite, nous verrons des algorithmes de quantification qui se d6composent naturellement selon le sch6ma 2-3 et p o u r lequel, en fait, l'obtention de l'indice i connaissant la valeur y est loin d'etre une op6ration triviale. M ~ m e si le croquis (2-4) correspond r a r e m e n t ~ la r6alit6, il a la vertu de mettre en relief la table de d6codage. En effet, pour g6n~raliser la notion de quantification h plus d ' u n e variable, il est pr6fdrable de ne plus recourir au concept de seuil mais d ' a p p r o c h e r le probl6me sous le seul angle de la table de d6codage. L a quantification devient alors une recherche de l'indice entre 0 et N 1
N o t e : D a n s le c a s scalaire o n p e u t tol6rer u n e certaine a m b i g u i t 6 s 6 m a n t i q u e e n t r e ~ quantification>> et ~ codage>) soit e n t r e v a l e u r a r r o n d i e Yl et indice i c o m m e il t r a n s p a r a i t clans l ' e x p r e s s i o n : ~< quantificateur logarithmique ~. Pr6cisons ce p o i n t s u r l ' e x e m p l e de la figure 1. Si la d i s t r i b u t i o n de x est r a i s o n n a b l e m e n t u n i f o r m e d a n s l'intervalle $ 3 , $4 la valeur a r r o n d i e s61ectionn~e, Ys e n l ' o c c u r r e n c e , se doit d ' 6 t r e proche de la m o y e n n e de ces d e u x seuils, c o m m e sugg6r6 p a r la droite e n pointill6 h 45 ~ Si ce n ' e s t p a s le cas, la t r a n s f o r m a t i o n repr6sent6e n ' o p ~ r e p a s u n e q u a n t i f i c a t i o n a u s e n s strict : elle a j o u t e u n c h a n g e m e n t d'6chelle o u r6f(~re i n d i r e c t e m e n t /l l ' i n d i c e i c o m m e clans le c a s d ' u n c o n v e r t i s s e u r MIC. 2[20
II.1.
Exemple simple.
L a figure 3 illustre une table de quantification d ' u n vecteur x ~t A l'entr6e i la table de d6codage cette fois un vecteur arrondi y~.
d6codage p o u r Ia deux dimensions. fait c o r r e s p o n d r e D a n s la figure 3,
~2 aO
90
20 30
x. 'l
70 10
6O 50
'1,JI2(4) ................ 4o
[u (4)] Y = Lw (4)J
120
x2, 9
I V1(4) x~
110
Xt
FIG. 3. - - P r i n c i p e de la q u a n t i f i c a t i o n vectorielle. L ' e n s e m b l e S des N = 13 v e c t e u r s a r r o n d i s d u q u a n t i f i c a t e u r vectoriel s o n t r e p r 6 s e n t 6 s s o u s f o r m e de p o i n t s d a n s l ' e s p a c e d e s c o o r d o n n 6 e s d u v e c : e u r d ' e n t r 6 e x. U n e e n t r 6 e x particuli~re est r e p r 6 s e n t 6 e d a n s le p l a n p a r u n r croix. L e v e c t e u r a r r o n d i le p l u s p r o c h e darts la t a b l e est le v e c t e u r y p o u r i = 4. O n s u p p o s e ici q u e la d i s t a n c e e u c l i d i e n n e est la d i s t a n c e / t m i n i m i s e r .
Principle o f vector quantization (VQ). The set S o f the N = 13 rounded-off values o f the vector quantizer are points in the input space x . A particular input x is symbolised by a cross. The nearest neighbour in the set is vector y with index i = 4. We assume that the distance to be minimized is the Euclidean distance. ANN. T~L~COMMUN., 41, n ~ 3-4, 1986
160
J.-P. ADOUL. -- LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
les N vecteuls de la table sont repr6sent6s par des points dans l'espace de leurs coordonn6es x~ et x2. L'indice i e s t donn6 /l la gauche de chaque point.
11.2.
Quantificateur optimal. IlI.1.
Un quantificateur vectoriel (QV) est compl~tement d6fini par un ensemble S de vecteurs arrondis et une distance d6finissant le degr6 de distorsion qui s'introduit l o r s q u ' u n vecteur d'entr6e x est approxim6 p a r un vecteur arrondi y. On utilisera la notation : d(x, Yl). Une distance telle que celle qui nous int6resse en quantification vectorielle est une fonction r6elle, non n6gative qui est utilis6e seulement aux fins de comparaisons. I1 s'ert suit que d(x . . . . ) peut ~tre de f o r m e assez g6n6rale [1]. L a seule exigence est que la distance d ' u n point h lui-m~me soit toujours plus petite que de ce point ~ tout autre point. En fait, dans la suite, nous ne consid~rerons que des distances de la f o r m e :
En particulier p o u r r = 2, d devient le calr6 de la distance euclidienne. N o u s utiliserons souvent cette distance qui, dans plusieurs situations, s'interpr6te directement c o m m e une puissance d ' e r r e u r de quantification. quantificateur
est
entibrement
ddfini par
son
Distribution gaussienne.
Ce qui peut paraltre curieux de prime abord, c'est que, m~me si les variables sont ind6pendantes, il y a avantage h utiliser la quantification vectorielle. Dans quelques rares cas pathologiques, les performances sont 6gales. Ceci s'explique tr6s simplement par l'observation q u ' u n ensemble de M quantificateurs scalaires est 6quivalent b. un quantificateur vectoriel particulier op6rant sur des vecteurs de dimension M. En effet, la figure 4 illustre ce fait sur
x2i
d(x, Y3 ---- lx - - Ylr"
(3)
Un
HI. COMPARAISON QUANTIFICATEURS SCALAIRES ET V E C T O R I E L S
ENTRE
9 9
,.."~"... :'0 0"..
"....
9
9
2
,,.,"0-.~
9
9 9
9 9
9
9
;'i.i r
"
"'".~ i......O"
9
a
O
ensemble S et la distance associ6e d(x, y) : (4)
Q(x) :
.vl tel que d(x, Yi) ~< d(x, y j) p o u r tout j :/: i, oh y~ et y j appartiennent ~t S. P a r ailleurs, si l ' o n connalt le n o m b r e N de vecteurs arrondis, la distance d(x, .) et la distribution conjointe du vecteur d'entr6e, p(x), on peut reconnaitre le q u a n t i f i c a t e u r o p t i m a l . C ' e s t de tous les quantificateurs, ou t o u s l e s ensembles S possibles, celui qui minimise l'esp6rance m a t h 6 m a t i q u e de la distance soit :
(5)
E(d) : f d(x, Q(x)) p(x) dx.
Construire un quantificateur qui p o u r une situation donn6e s ' a p p r o c h e des p e r f o r m a n c e s du quantificateur optimal est un art en soit. Duns le cas de quantificateurs scalaires p o u r la distribution gaussienne, les valeurs arrondies (et seuils) ont 6t6 tabul6es par M a x [2]. Les r6sultats correspondants ont 6t6 6tablis p a r Paez et Glisson p o u r les densit6s Laplace et G a m m a [3]. Il est convenable de parler du d d b i t binaire d'un quantificateur. Il s'agit bien stir de la transmission d ' u n indice i parmi N possibles ce qui repr6sente l o g 2 N bit. Il est souvent pratique de ramener le d6bit p a r dimension c o m m e par exemple p o u r permettre une c o m p a r a i s o n entre quantificateurs op6rant sur des vecteurs de dimensions diff6rentes. ANN. TI~L~COMMUN., 41, n ~ 3-4, 1986
FIG. 4 . - Comparaison de la quantification d'un v~cteur b. deux dimensions par une paire de quantificateurs scalaires optimaux (4a) et par un quantificateur vectoriel (4bL Les composantes du vecteur sont ind6pendantes et distrJ:u6es selon une lot normale. Comparison o f a dimensional vector quantization b3 a vec, , quantizer (4a) or by a vector quantizer (4b). The vector compo nents are free and obey a Gaussian distribution.
un exemple ~t deux dimensions. On y c o m p a r e la quantification d ' u n vecteur x selon deux approches diff6rentes. On suppose que les composantes du vecteur sont ind6pendantes et distribu6es chacune selon la lot normale. Duns la premi6re situation, on emploie une paire de quantificateurs scalaires que l ' o n applique /1 chaque c o m p o s a n t e s6par6ment. Ces quantificateurs sont o p t i m a u x (selon les tables de Max) avec un d6bit de 2 bits, soit Ns = 4 points (niveaux). Duns la deuxi6me situation, on utilise un quantificateur vectoriel obtenu par un algorithme it6ratif [1] ayant le m~me d6bit par dimension de 2 bits soit p o u r deux dimensions 2 ~ 22 ~ 8 points. Il apparalt clairement q u ' u n e paire de quantificateurs scalaires est 6quivalente 5. un quantificateur vectoriel dont les points sont au s o m m e t d ' u n e grille cart6sienne. Supposons maintenant que les c o m p o santes du vecteur d'entr6e aient en fait une certaine corr61ation. Rien ne change du c6t6 des quantificateurs scalaires par contre le quantificateur vectoriel 3/20
J.-P. ADOUL. -- LA QUANTIFICATIONVECTORIELLEDE FORMES D'ONDES
161
FIG. 6. - - Comparaison de deux m6thodes de quantification pour un vecteur x h deux dimensions r6parti uniform6ment sur le domaine. Deux quantificateurs scalaires (6a) et un quantificateur vectoriel b, motif hexagonal (6b). Le dernier est optimal pour le crit/:re de l'erreur quadratique moyenne. Fro. 5 . - Comparaison des performances entre une pai:e de quantificateurs sealaires et un quantifieateur veetoriel appliqub.s h u n veeteur h deux composantes gaussiennes ayant la corr61ation rho. En abscisse, on a le d6bit binaire par dimension. Les deux petits cercles montrent les quantificateurs de la figure 3. Performance comparison between a pair o f scalar quantizer and a vector quantizer applied to a bidimensional Gaussian vector with correlation rho. The rate is given in bit per dimension. The circles indicate the quantizers o f figure 3.
est capable de disposer ces vecteurs arrondis ~t bon escient. La figure 5 donne la performance en terme d'erreur quadratique moyenne du quantificateur vectoriel exprim6 en p o u r cent de la performance d ' u n e paire de quantificateurs scalaixes. Les r6sultats sont donn6s pour diff6rentes valeurs de la corr61ation et diff6rents d6bits par dimension.
III.2.
Distribution uniforme.
Supposons que nous ayons toujours b. faire h u n vecteur b, deux dimensions mais distribu6 cette fois de fagon uniforme sur un certain domaine et que nous comparions h nouveau les performances d ' u n e paire de quantificateurs scalaires et un quantificateur vectoriel. On suppose que le nombre de points est suffisamment grand p o u r pouvoir n6gliger les effets de bord, La figure 6 nous m o n t r e une portion de chacun des deux types de quantificateurs. A noter que l'on cherche h n o u v e a u des quantificateurs h d6bit comparables ; par cons6quent ils ont le m~me nombre de points et par suite la m~me densit6 moyenne. Ces deux motifs forment des r6seaux r6guliers. Le premier est c o u r a m m e n t appel6 le r6seau cubique ZM (pour M ~ 2 dimensions) et le second le r6seau hexagonal A 2 . P o u r conserver des densit~s de points comparables, il faut poser d z l d ~ : V/2-1~3- = 1,075. Le point le plus real quantifi6 est repr6sent6 dans les deux cas par un point blanc/~ distance rl et r2 respectid 2 / d l = 0,877. vement. Le r a p p o r t r 2 ] r l : ~ / 0 ~ 4/20
Comparison o f two quantization methods for a bidimensional vector x uniformly distributed : two scalar quantizers (6a) and a VQ with hexagonal pattern (6b), the latter is optimal f o r the Euclidean distance.
Nous voyons l~t la sup6riorit6 du second quantificateur. En fait, pour une distribution uniforme en dimension deux, N e w m a n [4] a montr6 que le r6seau hexagonal A2 conduit au quantificateur optimal p o u r l'erreur quadratique, soit 0,0796 par dimension (nombre ~t comparer h 0,0833 pour l'approche scalaire Z2). Ainsi un r6seau r6gulier conduit au quantificateur optimal. Une hypoth6se 6mise par Gersho veut que, pour toute dimension, il existe un r6seau r6gulier qui atteint ainsi les performances optimales. Cette hypoth6se jamais d6mentie n'est h pr6sent d6montr6e que pour les dimensions 2 et 3 [5]. Des r6seaux particuli6rement bons sont connus en dimensions 8 et 24. Nous allons montrer une m6thode de quantification qui exploite les propri6t6s de ces r6seaux p o u r q u a n tifier les formes d'ondes. Cette m6thode est appel6e quantification vectorielle sph6rique.
IV. Q U A N T I F I C A T I O N VECTORIELLE SPHI~RIQUE
IV.1.
Principe.
Nous nous t o u r n o n s maintenant vers le probl6me de quantifier efficacement les signaux 6chantillonn6s. Pour cela, nous d6coupons le signal en blocs de M 6chantillons. N o u s consid6rerons les M 6chantillons successifs de ces blocs c o m m e les M composantes de vecteurs b. M dimensions : X = [xl , x2 .... , xMY. La quantification vectorielle sph6rique consiste quantifier s6par6ment la n o r m e G (ou gain) et ANN. Ti~LI~COMMUN.,41, n~ 3-4, 1986
162
J.-1,. ADOUL. - LA QUANTIFICATIONVECTORIELLE DE FORMES D'ONDES
l'orientation x (ou phase) du vecteur X, soit : G = ~/~-~2
la n o r m e et
x = X]G
l'orientation ou vecteur normalis6.
Consid6rons en premier lieu la quantification de l'orientation. Cette quantification met en oeuvre un premier quantificateur Qo auquel est associ6e la table de d6codage So = [y~l i = l, 2 . . . . . N o - - 1]. Ce quantificateur op6re ~t un d6bit Ro : log2(No) et fournit le vecteur y~ qui minimise la quantit6 : d(x,y,) = Ilx-y,]] (6)
~,
= Ilxll ~ + Ily, ll ~ :
du quantificateur Q~(.) vers lequel nous tournons notre attention. Ce quantificateur op6re avec le d6bit RG e t a p o u r but d ' a p p r o x i m e r la quantit6 P G avec le moins de distorsion possible. R e m a r q u o n s que l'emploi de la formule (7 b) plut6t que (7 a), lorsqu'on quantifie l'orientation, permet d ' o b t e n i r la quantit6 P G directement sans calcul explicite de la norme G. Cette remarque nous conduit au diagramme de la figure 8.
2 xry,,
O
2 - - 2 xTyl.
X
\/
I1 est clair que minimiser cette distance revient /~ maximiser le produit scalaire xTy~ lequel produit s'interpr6te c o m m e la projection de l'orientation x sur le vecteur y~ (ou vice versa). Appelons P cette projection maximale : (7 a)
max,{xTy,} = m a x , { p r o j ( x ) / y , )
De faqon 6quivalente on peut calculer le produit scalaire directement ~ partir du vecteur non n o r m a lis6 X. Les calculs sont simplement mis /t l'6chelle par le facteur G. (7 b)
max,{Xry,) = m a x , { p r o j ( X ) ] y , }
= PG.
La figure 7 sch6matise une situation typique o/l le vecteur normalis6 x est approxim6 par y~. En fait,
t
Sphereunit~ enMdi~mio~ / I I x .r" / ,II N / 11 )3/a=X/G [ ]
"
fY= Q(X)= Qo(a)QG~PG) = Qo(x) /OE = IlO(X)-Xll ] Eh= IlO,o(a)-xll / E,:
FIG. 8. Diagramme de la quantification vectorielle sph6rique. Le quantificateur g!obal symbolis6 par le rectangle en pointill6s (cf. figure 2.2) se compose de deux quantificateurs l'un oI~rant sur l'orientation et l'autre sur PG, la norme corrig6e par la projection P. Ce diagramme correspond aux 6quations de la figure 7. -
= P.
!
&,
-
Basic block diagram for spherical vector quantization. The global quantizer is symbolized by the dotted box (cf. fig. 2.2) it is composed o f 2 quantizers : one for the a orientation )> and one for PG, the corrected norm. This block diagram corresponds to the equations o f figure 7.
On peut donc r6sumer ainsi les propri6t6s de la quantification vectorielle sph6rique. Appelant Q(.) le quantificateur 6quivalent nous avons : (8) (9)
Y~, = Q ( X )
= Qo(x) Qa(PG),
R = R0 + R ~ .
IV.2. Avantages de la quantification vectorielle sph6rique.
o,,~
P
T
f GE,
FIG. 7. - - Situation typique de quantification vectorielle sph6rique. La sph~.re de rayon unit6 est repr6sent6e par un arc de cercle. Le vecteur Yi retenu est celui qui conduit h la plus grande projection P. A typical situation o f spherical vector quantization. The unit sphere is represettted by a circle in the plane passing through the orighw, X altd Yi which yields the largest projection P.
c o m m e il apparait clairement sur cette figure, une meilleure a p p r o x i m a t i o n du vecteur x est donn6e par le vecteur P Y i puisque l'erreur commise est alors Eo qui reste toujours infdrieure /l E o . I1 s'en suit que la meilleure a p p r o x i m a t i o n p o u r le vecteur initial, X, serait P G y i si la quantit6 P G pouvait &re connue sans distorsion. En r6alit6, il convient de quantifier 6galement cette quantit6. C ' e s t le r61e ANN. T~L~COMMLrN.,41, n ~ 3-4, 1986
I1 y a plusieurs avantages importants /t quantifier s6par6ment n o r m e et orientation. Voici quelques-uns de ces avantages. a) Traiter la n o r m e /l p a r t r6duit bien entendu de un la dimension du problSme ( d ' u n volume 5, une surface dans R") et permet donc d'utiliser un dictionnaire de taille r6duite. b) Les avantages les plus importants viennent du fait que la n o r m e prdsente certaines particularit6s distinctives que l ' o n peut exploiter. Dans de nombreux cas pratiques, la n o r m e G varie de faqon lente d ' u n vecteur /1 l'autre. O n peut exploiter facilement cette forme de r e d o n d a n c e particuli6re par un codage du type pr6dictif. C ' e s t le cas du signal de parole p o u r lequel G 6volue /l une 6chelle de temps plus lente appel6e << r y t h m e syllabique >>. c) Dans plusieurs cas i m p o r t a n t s comme celui du signal de parole la n o r m e intervient, pour des raisons 5/20
J.-P. ADOUL. -- LA QUANTIFICATIONVECTORIELLE DE FORMES D'ONDES d ' o r d r e physiologique, par le biais d ' u n e 6chelle logarithmique. Quantifier sSparSment la norme permet alors de choisir librement le type d'Schelle qui lui est appropriS et de r6aliser facilement un quantificateur global offrant une compression de dynamique. d) On pourrait croire que quantifier vectoriellement le vecteur original X en le considSrant comme distribuS de fa~on uniforme dans un hypercube de M dimensions soit l ' a p p r o c h e la plus performante. En fait, loin de tendre vers l'uniformit6, la distribution de X est concentrSe dans une coquille sph6rique centrSe ~ l'origine. Ce phSnom6ne appel6 en anglais sphere hardening se produit quand les composantes du vecteur ne sont pas de natures diffSrentes mais Smanent d ' u n e mSme source. Illustrons cette derni6re observation en consid6rant le cas d ' u n e source gaussienne d'Schantillons x, indSpendants. Si l ' o n f o r m e ~t partir d ' u n e telle source des vecteurs de dimension M le carr6 de leur norme est distribuS selon la distribution dite du chi-deux avec M ~ 1 degrSs de libertS. L a n o r m e (c'est-~t-dire la racine carrSe d ' u n chi-deux) peut ~tre assimil6e ~t une variable gaussienne de m o y e n n e Go et de variance G~](2 M 1) [6]. Ainsi p o u r les dimensions 8 et 24, l'6cart-type de la n o r m e G autour de sa valeur moyenne reprSsente respectivement 26 et 15 % de cette valeur moyenne.
IV.3. Approche statistique et approehe algfbriqae. La quantification de l'orientation en QVS peut &re r6alisSe par dictionnaires stockgs obtenus par l'approche statistique en particulier en appliquant un algorithme du type K-moyennes [1] fi un ensemble de vecteurs normalisSs d'apprentissage (orientations). Cette approche est r e c o m m a n d S e quand la distribution des orientations sur la sph6re unit6 est franchement non uniforme. L ' a l g o r i t h m e d'apprentissage permet alots de tirer parti au m a x i m u m de cette non-uniformit6. La deuxi6me approche, dite algSbrique consiste h faire usage des proprigtSs des r6seaux rSguliers p o u r constituer des dictionnaires de points sur une hypersph6re unitS. Cette deuxi6me approche sera appropriSe dans Ie cas o0 les orientations sont raisonnablement uniform6ment distribuSes sur la sph6re. Si cette condition est v6rifiSe, l ' a p p r o c h e alg6brique offre des avantages tr6s importants par rapport fi l ' a p p r o c h e statistique. Ces avantages sont les suivants. a) Le dictionnaire n ' a pas h 8tre stocks car Ies vecteurs y~ s'obtiennent, c o m m e nous le verrons plus loin, p a r p e r m u t a t i o n s des composantes de vecteurs particuliers appelSs directeurs (<< leader >> en anglais) ; ces directeurs qui sont en petit nombre, sont stockSs. b) La recherche du plus proche voisin est accSl6rSe car elle s'op6re seulement au niveau des directeurs. c) La cons6quence des deux points ci-dessus est 6/20
163
que l ' a p p r o c h e alg6brique p e r m e t d ' e n v i s a g e r des dictionnaires beaucoup plus grands, par exemple 100 ~t 10 000 fois plus grands que p o u r l ' a p p r o c h e statistique ou d'envisager des dimensions plus i m p o r tantes. U n e pr6occupation nouvelle surgit dans l ' a p p r o c h e par r6seau : le probl6me de la num6rotation. En effet, lorsque le plus proche voisin y a 6tS trouv6, il faut en plus dSterminer son rang i darts la collection S. C o m m e n t utiliser les rSseaux p o u r constituer des quantificateurs sph6riques ? P o u r rSpondre fi cette question, considSrons plus en dStail la dSfinition et les propriStSs des r6seaux.
V.
V.1.
RI~SEAUX R I ~ G U L I E R S DE POINTS
R6seau et empilement de sph6res.
L'6tude des r6seaux r6guliers est 6troitement li6e au probl6me de l'empilement de sph6res de mSme diam~tre dans R M [7]. Dans ce dernier probl6me, il s'agit de disposer les sph6res de maniSre /~ obtenir l ' e m p i l e m e n t le plus dense ( r a p p o r t du v o l u m e des sph6res sur le volume occup6). P a r exemple en dimension 2, la fa~on la plus dense << d ' e m p i l e r >> des sph6res, disons serrer des pi6ces de m o n n a i e sur un plan, c'est encore l ' a r r a n g e m e n t hexagonal, le centre des pi6ces f o r m a n t le r6seau de points de la figure 6 b. P o u r ce qui est de trois dimensions, pensons b. des boules de billard. N o u s p o u v o n s d6j~ les disposer de fa~on optimale sur un plan en f o r m a n t une premi6re couche selon l ' a r r a n g e m e n t hexagonal. N o u s pouvons ensuite poser une deuxi6me couche identique mais d6cal6e de mani6re/L ce que les boules occupent les
> de la premi6re couche. On continue ainsi ~ placer une troisi6me couche. L a figure 9 m o n t r e les deux fa~ons de mettre la troisi6me
Flo. 9 . - Deux empilements de sph6res en 3 dimensions obtenus en superposant des couches d'arrangement hexagonal. La troisi6me couche peut ~tre en coincidence avec la premiere (9a) ou non (9b). Les centres des sph6res de la figure 9b forment un r6seau r6gulier de points. On passe des couches 1 ~ 2 et 2 ~ 3 par la m6me translation sugg6r6e par la fl6che. Two sphere packings in three dimensions obtained by stacking layers o f hexagonal arrangements. The top layer can coincide with the first (9a) or not (9b). The sphere centers in figure 9b form a regular point lattice. The translation from layer 1 to 2 and from 2 to 3 is suggested by the arrow.
ANN. T~L~COMMUN., 41, n ~ 3-4, 1986
164
J.-P. ADOUL. - LA QUANTIFICATIONVECTORIELLEDE FORMES D'ONDES
couche. Les deux empilements illustr4s ont la m~me densitG cependant seul l'empilement de la figure 9 b correspond h u n r6seau r6gulier.
V.2.
D6finition d'un r4seau.
U n r6seau r6gulier dans R u est l'ensemble de points x qui s'obtiennent par combinaison lin6aire de M vecteurs de base ind6pendants, z t , z2 . . . . . z ~ , avec des coefficients de proportionalit4 entiers, k t , k 2 , ..., k M : (10)
L~
-~ ( x l x
~ ~ k~z,} ;
de ~< 1 )> qu'il contient. U a code corrigera t erreurs si la plus petite distance de Hamming, dnmin, entre paire de ses M-uplets est sup6rieure ~. t [ 2 . Enfin, les propri6t6s globales d ' u n code se r6sument par les trois entiers : [M, log2N, dnmin]. Ainsi, le code de la figure l0 est un code [3, 1, 3]... Leech et Sloane ont propos4 [8] diverses constructions de r6seaux ~t partir d ' u n code correcteur d'erreurs, C [ M , log2N, d,]. La c o n s t r u c t i o n A consiste ~. prendre t o u s l e s points de ZM qui sont congrus, m o d u l o 2 par composante, ~ un mot du code C :
01)
L = {xlx = I x , ,
.....
xM]
zM
et [Xlmo~2 , X2mod2 ..... X , mod2] ~ C}.
k , entier.
1
Par exemple, le r4seau hexagonal, A 2 , de la figure 6 b est obtenu ~t partir des vecteurs de base z~ = [1, ~/3], z2 = [2, 0]. Remarquons tout de suite q u ' u n r6seau r6gulier reste invariant l o r s q u ' o n le translate pour amener son origine h l ' u n quelconque de ses points.
V.3.
R6seaux et codes correcteurs d'erreurs.
Plusieurs m6thodes de construction de r6seaux ont p o u r point de d6part les codes correcteurs d'erreurs. En effet un code (bloc) correcteur d'erreurs, disons binaire, est un sous-ensemble de N M-uplets binaires parmi les 2 u possibles (sommets de l'hypercube unit6 dans RU). N e s t g6n6ralement une puissance de 2. U n exemple tr6s simple est donn6 par le code dit r4p6tition qui met en ~euvre N = 2 triplets binaires parmi les 8 ----- 23 possibles. Ce code est illustr6 la figure 10. Lors de la transmission d ' u n mot de code, la valeur binaire peut se trouver invers6e (erreur due au canal) sur quelques positions du M-uplet. O n appelle distance de Hamming, d . , entre deux M-uplets le nombre de positions sur lesquels ceux-ci diff6rent. Par exemple, la distance entre les deux quadruplets suivants est dn([1 1 0 0], [1 0 0 1]) - : 2. On appelle aussi <~poids >~d ' u n m o t de code le hombre
Cela signifie que si l ' o n 6crit les composantes enti6res xi en repr6sentation binaire << c o m p l ( m e n t d d e u x >> le M-uplet form4 par le bit de plus faible poids de chaque composante est un mot du code C. Encore une autre faqon de consid6rer cette construction c'est de remarquer q u ' o n peut 6crire : x = y + c ; oh e E C et o h y est un vecteur du r4seau ~t composantes paires : 2 ZM. Le vecteur y 4tant obtenu en forqant ~t 0 les bits de plus faible poids des composantes de x. I1 s'en suit que le r6seau L peut s'6crire c o m m e l'union de copies du r6seau 2 Z ~ translat6es par un vecteur du code : (12)
13= |Io,
Rien ne nous emp~che de voir dans cette formule, bien stir, l ' u n i o n des copies du code C translat6es aux sommets du r6seau a composantes paires comme l'illustre la figure 11.
'O z. 9
10.-
Interpretation g6om~trique du code ~ r~p6tition
C[3,1,3]. Chacune des trois composantes du triplet [xt, x~, xa] ne pouvant prendre que les valeurs 0 ou 1, il y a 8 triplets possibles qui sont les huit sommets du cube unit6. Le code h. r6p6tilion est le sous-ensemble de N = 2 sommets les plus 61oign6s possible soit b. distance euclidienne d = ~/3- et distance de Hamming d n = 3. Geometrical interpretation o f the C[3,1,3] repetition code. Each component o f the triplet [ x l . x~, xa] can take only the value 0 or 1. There are 8 possible triplets which are the vectices o f the unit cube. The repetition code is a subset o f N = 2 vertices furthest apart namely Euclidean distance d = ~ and Hamming distance d H = 3.
ANN. T~L~COMMUN., 41, n ~ 3-4, 1986
9 x2
.~.:.:.:.:
"i"'ir
'i
~i ~ ...:-:.:-:.:. ! .........:""
.."!',
o, o1, [1, l, t ] |
9(,2
FIG.
06 c ~ C .
i
xj/T
x3o
L = O 2 Z M + el ;
FIG. 1 1 . - R6seau r6gulier obtenu par la construction A appliqu6e au code b. r6p6tition de la figure 10. La figure lla montre le code C et le premier cube (2 • 2 / 2) du r6seau 2ZM . La figure 1lb illustre une r6gion du r6sultat de la construction. Le r6seau obtenu s'appelle cubique centr6 An*; il est le dual de l'empi!ement de la figure 9b. A regular lattice obtained by construction A applied to the repetition code o f figure 10. Figure l l a shows code C and the cube (2 x 2 x 2) f r o m the 2Zrn lattice and figure l l b the results o f construction A. The lattice obtained is called A3* it is the dual o f the lattice o f figure 9b.
Un autre r6seau important par la suite est le r6seau DM. II contient les points de ZM tels que la somme de leurs composantes soit paire. (C'est aussi le r6sultat de la construction A appliqu6e au code ~ simple 7/20
J.-P. ADOUL. -- LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
165
Le r6seau de Leech s'obtient en superposant deux versions de 2 L24 d6cal6es par un vecteur de translation u ; c'est pourquoi on se r6f6re ~ L24 c o m m e le demir6seau de Leech, (16) A24. = 2 L24 LI2 L24 -~ u ; oh u = [ - - 3, 1, 1, 1. . . . . 1].
L
V-
9
Y
--
FIG. 12. - - R6seau D M pour 2 et 3 dimensions. Lattice D M for 2 and 3 dimensions.
parit6 [M, M ~ 1, 2].) P o u r la dimension deux, D2 est en forme de damier. La figure 12 illustre DM pour 2 et 3 dimensions. G r a c e b. DM, on peut obtenir des r6seaux par la construction B. On consid6re un code lin6aire C d o n t le poids des roots est divisible par 4. Cette construction consiste /~ prendre t o u s l e s points de D u qui sont congrus, modulo 2 par composante, ~t un m o t de C. Off encore, on peut f o r m e r le rdseau c o m m e l'union de r6seaux 2 D u translat6s par chaque m o t cl du code C. (13)
L =
U 2 D M - F - Cl ; i
O/a c ~ C .
Les r6seaux connus Ies plus int6ressants p o u r la quantification vectorielle sph6rique sont les r6seaux suivants : 9 le r6seau de Gosset E8 en huit dimensions, 9 le r6seau de Barnes-Wall Ax6 en 16 dimensions et 9 le r6seau de Leech A24 en 24 dimensions. Nous allons d6finir ces trois r6seaux et approfondir en particulier Es et A 2 4 . Le rdseau de Gosset est d6fini c o m m e l'union de 2 r6seaux 2 Ds translat6s par les deux mots du code ~t r6p6tition : [0, 0 . . . . . 0] et [1, 1, ..., 1]. Soit : (14)
Es = 2 D s
U2Ds
+ 1 ;
L24 =
t.I 2 D24 --[- Ci ; i
8/20
R~seaux et quantification uniforme.
Avant de nous pencher sur l'exploitation de ces r6seaux en Qvs, il convient de citer leur p e r f o r m a n c e en quantification de la distribution uniforme c o m m e illustr6 sur la figure 6 b. Ces r6sultats ont 6t6 obtenus par Gersho [12], Sloane et C o n w a y [13] [14]. D a n s cette situation, les points du quantificateur sont les sommets Yi du r6seau consid6r6 si bien q u ' u n point x de R M est arrondi ~t la valeur yi qui minimise le cart6 de l'erreur d ' a r r o n d i . Autrement dit la distance utilis6e est : d(x, Yi) = (x - - y l ) 2 . P o u r un quantificateur, on d6finit la rdgion de Vorono~ autour d ' u n point y~, d6not6e V~, c o m m e l'ensemble des points de R M qui sont quantifi6s p a r Yt , (17)
V, = { x l x ~ R M e t d(x - - y , )
<~ d(x - - y j ) } .
C o m m e un r6seau r6gulier reste congru & luimSme l o r s q u ' o n le translate p o u r amener son origine Yo 5. un point quelconque y , , toutes les rfgions de Voronoi sont identiques 5. V 0 . Pour la distance consid6r6e, cette r6gion est un poly6dre r6gulier. La figure 13 illustre Vo dans le cas des r6seaux hexagonal et cubique centr6. Pour un quantificateur utilisant un r6seau r6gulier appliqu6 ~t la densit6 uniforme, l'erreur q u a d r a t i q u e moyenne normalis6e El est la m~me p o u r toute r6gion V~. D6s lors, la p e r f o r m a n c e globale E est u n i q u e m e n t li6e aux propri6t6s g6om6triques de la r6gion V o . En effet, E ] d i m est donn6 par la relation suivante ;
off 1 = [1, 1..... 1].
II existe plusieurs d6finitions de E s . Par exemple la construction A appliqu6e au code de H a m m i n g 6tendu [8, 4, 4] [9], ou ~ partir de vecteurs de base qui sont les rang6es de la matrice de H a d a m a r 8 • 8 [ 10] etc. Le rdseau de Barnes-Wall se d6finit aussi par la construction B appliqu6e au code Reed-Muller du premier ordre [16, 5, 8] qui contient 32 mots de 16 bit [9]. Le r6seau dual peut s'obtenir 6galement b. partir du code de H a m m i n g 6tendu [16, 11, 4] [l 1]. Enfin le r~seau de L e e c h se d~finit par une construction d ' u n type similaire h B faisant intervenir le code de G o l a y 6tendu : 924[24, 12, 8] qui contient 4 096 mots de 24 bit. O n appelle L24 le r6seau obtenu en appliquant la construction B au code ~24. (15)
V.4.
9
O~1 Cl ~ 924 .
FIG. 1 3 . - R6gions de Voronoi pour lcs r6seaux r6guliers hexagonaux (13a) et le r6seau cubique centr6 (13b). Ce sont les deux seuls r6seaux pour lesquels, jusqu'b, pr6sent, existe une preuve formelle qu'ils conduisent h l'erreur quadratique minimale en 2 et 3 dimensions respectivement. Voronoi regions for the hexagonal lattice (13a) and the cubic centered lattice (13b). These are the only two multidimensional lattices for which a formal proof of optimality exists to this date.
ANN. T~LI~COMMUN.,41, n ~ 3-4, 1986
166
J.-P. ADOUL. - LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
les int6grales 6 t an t effectu6es sur la r6gion Vo :
= ~ (17)
1
[
i
dxI(M+2)/M
.,x~vo X~ dX l [ .~x~Vo J
E/dim
C e t t e q u a n t i t 6 est a p p e l 6 e le m o m e n t d ' i n e r t i e d ' o r d r e 2 n o r m a l i s 6 et sans d i m e n s i o n de la r~gion de V o r o n o i [13]. Elle p e r m e t la c o m p a r a i s o n entre r6seaux de d i m e n s i o n s diff6rentes. Le t a b l e a u I r 6 s u m e les p e r f o r m a n c e s des m e i l l e u r s r6seaux c o n n u s . TABL. ].
~ Performances de la quantification d'une densit6 uniforme par les m~illeurs r6seaux connus.
MSE performances for best lattices known. R6seau
Dim.
E/dim.
FIG. 14. - - Sph6res concentriques de rayons croissants contenant les points de A2.
Concentric shells of htcreasing radius containing the points of Aa . Quantificateur scalaire Hexagonal Cubique centr6 Damier Gosset Barnes-Wall Leech
A1
1
A~
2 3 4 8 16 24
A~' D4 A16
0,0833 0,0802 0,0785 0,0766 0,0717 0,0683 0,0658
Conway et Sloane [15] d6crivent des algorithmes optimaux et rapides (pour E8 tout au moins) pour trouver le point du r6seau le plus proche du point quantifier. En pratique, pour utiliser un r6seau, il faut consid6rer une r6gion finie : l'int6rieur d'un hypercube ou encore mieux d'une sph6re. Ces auteurs ont pr6sent6 un algorithme tr6s 616gant et rapide [16] pour num6roter les points d'un r6seau dans un volume sph6rique lorsque le nombre des points est de la forme N = 2 TM (c'est-h-dire un nombre entier de bit par dimension). En QVS, nous utiliserons le r6seau de fagon un peu diff6rente comme nous allons le voir dans la section suivante.
VI. QUANTIFICATION VECTORIELLE SPHI~RIQUE A PARTIR DE RI~SEAUX
VI.1.
le r6seau peut s'envisager comme l'union des points qui appartiennent h des spheres concentriques de rayons croissants. La figure 14 illustre cela dans le cas du r6seau hexagonal. Sur la figure 14, on constate que pour A2 le rayon des sph6res ne croit pas de fagon bien r6guli6re et que le nombre de points n'augmente pas d'une sph6re /t l'autre de fagon trSs ordonn6e. Enfin sur la 4e sph6re, les points ne sont pas uniform6ment r6partis. Le tableau II donne les nombres de points des 5 premi6res sph6res autour de l'origine. Les anomalies relev6r pour A2 disparaissent pour les r6seaux de dimensions 8, 16 et 24. Pour ces dimensions, le rayon des sphSres successives croit de faqon ordonn6e proportionnellement ~t ~/m-; m prenant des valeurs enti6res successives. L'entier m devient alors ua indice naturel pour ordonner les sph6res du r~seau. Les quantificateurs sph6riques seront construits ~ partir des points d'une sphere donn6e une fois normalis6s par le rayon de la sphere ou par l'union, apr6s normalisation, de plusieurs sph6res. Les spheres cons6cutives &ant compl6mentaires puisque les points d'une sphSre sont vis-a-vis des <~trous >> les plus profonds de la sph6re adjacente.
VI.2. Quantification sph6rique avec le r6seau de Gosset.
Inventaire des r6seaux performants.
Les points d'un r6seau appartiennent h une certaine sph6re centr6e sur l'origine. Vu sous cet angle,
Pour le r6seau de Gosset, on d6notera par Es(m) l'ensemble des points d'une sph6re et par Ns(m) le
TABL. II. - - Nombre de points sur les 5 premi6res sph6res des r~seaux discut6s.
Number of pom~ on the first five spheres for the discussed latt~e.
1
A N N . T~L~COMMUN.,
2 [ j
6
L 12
41, n ~ 3-4, 1986
Dr
E8
24 24 96 24 144
240 2160 6720 17520 30240
A16 4320 61440 522720 2211840 8960640
L2~ 98256 8384512 199066704 2314125312 17213014208
A24 196560 16773120 398034000 4629381120 34417656000
9/20
J.-P. ADOUL. - LA QUANTIFICATION VECTORIELLE DE FORMES D~ONDES n o m b r e de p o i n t s d e eet e n s e m b l e (19)
Es(m)
=
167
TABL. IV. - - Liste des directeurs des 8 classes d'6quivalence de la sph6re m = 1 avec le nombre d'616ment K(j) de chaque classe et le cumul K(j) des classes pr6c6dentes.
:
(YIY ~ Es N S,.},
List o f the 8 classes leader for the sphere m = 1 along with the number o f points per class, K ( j ) , and the cumulative number o f points o f that class, K ( j ) .
off S,. est la sph6re d e r a y o n 2 x/2-m. E s ---- U Ea(m). m
Si l ' o n utilise E s ( m ) c o m m e quantificateur, n o u s a v o n s t o u t u n c h o i x d e d 6 b i t s p a r d i m e n s i o n suivant la sph6re m utilis6e. Le t a b l e a u I I I d o n n e p o u r c h a q u e s p h e r e m e n t r e 1 et 15 le n o m b r e N s ( m ) et le d6bit correspondant en bit/dimension. TABL. III. - - Inventaire des spheres de Es 9 A chaque sph6re m entre 1 et 15 correspond Pro, le nombre de classes, Ns(m), le nombre de points et le d6bit correspondant en bit/dimension. List o f shells o r e s . For each sphere from m = 1 to 15 the number o f classes, I'm, the number o f lattice points, Ns(m), and the rate in bit~dim, are given. m
Pm
Ns(m )
D6bit/dim.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
8 15 24 42 54 57 103 119 124 162 220 208 279 305 343
240 2160 6720 17520 30240 60480 82560 140400 181680 272160 319680 490560 527520 743040 846720
0,988 1,385 1,589 1,762 1,861 1,986 2,042 2,137 2,184 2,257 2,286 2,363 2,376 2,438 2,461
A y a n t r e t e n u une sph6re m, n o u s p o u v o n s o r d o n n e r les p o i n t s e n t r e 0 et Ns(rn) - - 1, ce qui c o n s t i t u e les vecteurs Yt de n o t r e q u a n t i f i c a t e u r ( i g n o r a n t la quest i o n de n o r m a l i s a t i o n ) . D e u x p r o b l 6 m e s restent h r 6 s o u d r e p o u r e x p l o i t e r ce q u a n t i f i c a t e u r : a) t r o u v e r le p l u s p r o c h e v o i s i n y d u vecteur quantifier x, b) et d & e r m i n e r l ' i n d i c e i d e ce voisin. N o u s a l l o n s d 6 c r i r e u n a l g o r i t h m e tr6s efficace p o u r r 6 s o u d r e ces d e u x p r o b l 6 m e s . U n e propri6t6 de Es(m) p a r t i c u l i 6 r e m e n t i n t 6 r e s s a n t e est que t o u t e p e r m u t a t i o n des c o o r d o n n 6 e s d ' u n v e c t e u r de cet e n s e m b l e est elacore u n v e c t e u r de cet ensemble. Cette propri6t6 nous permet de dffinir une relation d'6quivalence entre vecteurs que nous d6noterons ~. N o u s d i r o n s q u e les v e c t e u r s y e t z de Es(m) sont 6quivalents, y ~ z, s'ils se d 6 d u i s e n t l ' u n de l ' a u t r e p a r p e r m u t a t i o n des c o m p o s a n t e s . P a r exemple, les vecteurs s u i v a n t s s o n t 6 q u i v a l e n t s : [2, 0, 0, 0, ~
2, 0, 0, 0] ~, [ 0 , 0 , - - 2 , 0 , 0 , 2 , 0 , 0 ] .
C e t t e r e l a t i o n d ' 6 q u i v a l e n c e i n d u i t une p a r t i t i o n de l ' e n s e m b l e E s ( m ) e n Pm classes. Ce n o m b r e pm est 6 g a l e m e n t t a b u l 6 d a n s le t a b l e a u IV. 10/20
J 1 2 3 4 5 6 7 8
K(j) H(j)
Directeurs (m = 1)
0 28 84 85 113 183 211 239
2 2 0 0 0 0 2 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 --1 --1 1 1 --1 --1 --1 --1 0 0 0 0 0 0 --1 --1 --1 --1 --1 --1
28 56 1 28 70 28 28 1
0 0 1 --1 --1 --1 -- 2 --1
0 -- 2 1 --1 --1 --1 --2 --1
D a n s c h a c u n e des classes o n <> les vect e u r s d a n s l ' o r d r e l e x i c o g r a p h i q u e et l ' o n b a p t i s e le p l u s g r a n d d ' e n t r e e u x << d i r e c t e u r d e la classe >> ( t o u j o u r s par rapport h l'ordre lexicographique). Les P,, d i r e c t e u r s s o n t a l o r s e u x - m ~ m e s o r d o n n 6 s d a n s l ' o r d r e l e x i c o g r a p h i q u e p a r l ' i n d i c e j = 1, 2 . . . . , P , , . L e t a b l e a u I I d o n n e p o u r la sph6re m = 1 l a liste des P~ -----8 d i r e c t e u r s . D a n s cette t a b l e , o n t r o u v e d e p l u s la c a r d i n a l i t 6 de la classe, K ( j ) , ainsi q u e H ( j ) , le c u m u l des c a r d i n a l i t 6 s des classes p r 6 c 6 d e n t e s (c'est-~t-dire de 1 h j 1). O n p e u t n o t e r en p a s s a n t q u e c h a q u e classe r e p r 6 sente u n c o d e d e p e r m u t a t i o n s i n t r o d u i t p a r S l e p i a n [16] et utilis6 p a r B e r g e r c o m m e q u a n t i f i c a t e u r vect o r i e l [17]. A i n s i d a n s le cas d e 8 d i m e n s i o n s , le r 6 s e a u d e G o s s e t n o u s i n d i q u e la f a g o n o p t i m a l e d e g6n6raliser la n o t i o n de c o d e de p e r m u t a t i o n s 5. celle de l ' u n i o n de plusieurs codes de permutations. A p p e l o n s q le n o m b r e d e v a l e u r s d i s t i n c t e s q u e p r e n n e n t les c o m p o s a n t e s d u d i r e c t e u r . O n d 6 n o t e a l o r s , w o, le n o m b r e d e r 6 p 6 t i t i o n s d e la p l u s g r a n d e c o m p o s a n t e a o , w ~, le n o m b r e d e r 6 p 6 t i t i o n s d e la d e u x i 6 m e p l u s g r a n d e v a l e u r a l et ainsi d e suite j u s q u ' h w q - l , le n o m b r e d e r 6 p 6 t i t i o n s d e la p l u s p e t i t e v a l e u r a ~ _ l 9 P a r e x e m p l e , p o u r le 6 e d i r e c t e u r d u t a b l e a u IV, n o u s t r o u v o n s q = 2 v a l e u r s d i s t i n c t e s p o u r les c o m p o s a n t e s , soit ao = 1 et a l = - - 1. Les n o m b r e s d e r 6 p 6 t i t i o n s s o n t p a r c o n s 6 q u e n t w 0 ---- 2 et w z = 6. L a c a r d i n a l i t 6 d ' u n e classe est d o n n 6 e p a r la f o r m u l e d 6 n o m b r a n t les p e r m u t a t i o n s avec r6p6titions. Soit : (20)
K(j) :
8 !](w ~ ! w t ! w 2 ! ... w ~-1 !).
P o u r i n d e x e r les K ( j ) p e r m u t a t i o n s de la classe, n o u s a v o n s b e s o i n de g 6 n 6 r a l i s e r q u e l q u e p e u les n o m b r e s w d en l e u r a d j o i g n a n t u n i n d i c e k d e la f a g o n s u i v a n t e . U n v e c t e u r q u e l c o n q u e d e la classe j c o m p t e t o u j o u r s , b i e n stir, q v a l e u r s d i s t i n c t e s d a n s ses c o m p o s a n t e s qui s o n t p e u t - S t r e d a n s le d 6 s o r d r e . C o n s i d & a n t l ' i n d i c e p a r t i c u l i e r , d, o n d6finit w~ c o m m e le n o m b r e des rdp~titions de la valeur an q u i r e s t e n t d a n s les p o s i t i o n s k ~ M ( M = 8). L e c a l c u l des n o m b r e s ANN.
TELt~COMMUN.,
41, n ~ 3-4, 1986
168
J.-P.
ADOUL.
.'~, est illustr6 ci-apr6s p o u r le cas d ' u n vecteur y de la sph6re 9 d o n t le directeur est [4, 4, 4, 4, 2, 2, 0, 0] T. L a fen~tre 5. consid6rer dans le cas de l'indice k = 6 est montr6e p a r un rectangle en pointill6. positionk: .
!
= [4,
2 3 4 5 6 7
8
Algorithme de quantification pour une sphkre de E s . Soit x = [ x l , x2 .... , Xs] v un vecteur 5. huit c o m p o santes r6elles 5. quantifier par Es(m), les vecteurs de la sph6re m. L ' a l g o r i t h m e se d6compose naturellement en quatre 6tapes.
Etape 1 : r6ordonner les c o m p o s a n t e s du vecteur p a r ordre d6croissant des valeurs (c'est-5.-dire plus grande valeur en position 1). Appelons .~ ce nouveau vecteur. Etape 2 ." trouver le directeur j * le plus proche en cherchant p a r m i t o u s l e s directeurs celui qui conduit au plus g r a n d produit scalaire : 1, 2 ..... Ns(m)}).
Etape 3 : d6terminer le rang t du vecteur 5. l'int6rieur de la classe j * p a r la formule (21). Etape 4 : d6terminer l'indice i du vecteur quantifi6 y , par : i ----- t + H ( j * ) = 0, 1. . . . . N s ( m ) - -
1.
Fin. R e t r o u v e r le vecteur y, 5. partir de son indice i se fait essentiellement p a r les op6rations inverses. Algorithme de ddcodage. Etape 1 : retrouver la c l a s s e j * 5. laqueIle appartient le vecteur j * tel que : (24)
H ( j * ) ~< i < H ( j * + 1).
ANN. T~LI~COMMUN.,41, n ~ 3-4, 1986
(25)
t -= i - - H(j*).
vectorielle spMrique bas~e sur
Le r6seau de Leech fut d6couvert par Leech [18] et explor6 p a r Sloane et en particulier Conway [19]. Ce r6seau pr6sente des propri6t6s t o u t / t fait uniques. En particulier, sa densit6 est tr~s grande, le point le plus mal quantifi6 ne se trouve qu'5_ 1]~/2- lois la distance minimale entre les points du r6seau [20]. Les propri6t6s de ce r6seau d6coulent du code de Golay 6tendu ~2, dont nous rappelons quelques propri6t6s. VI.3.1.
avec la convention que : 0 ! = 1 et ( - - 1) ! = ~ ; ( M = 8).
(23)
D'ONDES
Etape 2 : retrouver le rang t dans la classe j * v6rifiant :
VI.3. Quantification le r~seau de Leech.
i=O [:r
maxs({~r~cs[ j :
DE FORMES
Fin. T o u r n o n s - n o u s 5. pr6sent vers le r6seau de Leech et son exploitation.
2, 4, O, 0,i4, 4, 21i
La formule du rang de Schalkwijk [39] nous permet de trouver l'index lexicographique t d ' u n vecteur p a r m i les K ( j ) m e m b r e s de sa classe 5. partir de ses n o m b r e s w~. Le rang est donn6 p a r la formule suivante o~ d(k) est l'indice d de la k-i6me c o m p o s a n t e : aa(k). a d(k)-I (M--k) ! (21) t = Z Z q-1 , k=l a=o (wka__ 1 ) ] I - I ( w ~ ! )
,~T~j'k =
VECTORIELLE
Etape 3 : il faut faire subir au directeur .~ de la classe j * la p e r m u t a t i o n (inverse) qui le (era passer du rang K ( j ) - - 1 au r a n g t [40].
%.,.
(22)
-- L A Q U A N T I F I C A T I O N
Code de Golay.
Le code de G o l a y 6tendu ~24 [24, 12, 8] est un code lin6aire form6 de 212 = 4 0 9 6 mots de 24 bits. I1 existe un n o m b r e consid6rable de versions du code de Golay 6tendu qui sont toutes identiques 5. une permutation des c o m p o s a n t e s pr6s. Une version int6ressante est celle de Wolf'mann [21] qui pr6sente les sym6tries les plus remarquables. Les mots de G o l a y se r6partissent en 5 groupes de poids, soit : poids 0 poids 8 poids 12 poids 16 poids 24 total
1 759 2 576 759 1 4 096
m o t nul octades dod6cades mots de 16 bits m o t [1, 1, 1, 1. . . . , 1] mots
Les 759 octades f o r m e n t un syst6me de Steiner S (5, 8, 24). C'est-5.-dire que p o u r tout groupe de 5 coordonn6es, il existe une et une seule octade qui le couvre. Consid6rons m a i n t e n a n t un m o t binaire quelconque de 24 bit, il y e n a 224 ----- 16 777 216. Bien que la chance de t o m b e r sur un m o t de code soit faible (1[4 096), il y a toujours un m o t de code ~t distance 4 ou moins. Ceci m o n t r e combien Ie code G2. occupe efficacement l ' h y p e r c u b e unit& Cette propri6t6 est utilis6e pour la correction d'erreurs. En effet, si le m o t de code c~ a 6t6 perturb6 sur une, deux ou trois positions, le m o t r6sultant ~t (qui est ~. distance de H a m m i n g 1, 2 ou 3) peut ~tre corrig6 sans ambiguit6 en cherchant le m o t de g 2 . le plus proche. Si quatre erreurs ont 6t6 commises, 11/20
J.-P. ADOUL. - LA QUANTIFICATIONVECTORIELLEDE FORMES D'ONDES on ne peut retrouver le mot original sans ambiguit6 ; cependant, on sait parmi quel groupe de six mots de ~2~ il se trouve. La fonction qui permet de recouvrir le mot c~ (ou le groupe des 6 candidats) s'appelle le d~codeur D : el = D(~). VI.3.2.
Spheres de
A24.
C o m m e p o u r le r6seau de Gosset, nous d6finissons par Az,~(m ) l'ensemble des points de A24 qui se trouvent sur la sph6re de rayon 4~/m-. Pour les valeurs positives ou nulles de m, A2#(rn) op6re une partition exhaustive de A2~. Le hombre N2~(m) de points de l'ensemble A24(m ) est donn6 dans le tableau V. - - Caract6ristique des 20 premi6res spheres du r6seau de Leech ; m est le num6ro de la sph6re, N(m) le nombre de points qu'elle contient avec ce que cela repr6sente au point de vue d6bit par 6chantillons. P(m) est le nombre de classes et PP(m) le nombre de sous-classes quand on consid&e les contraintes impos~es par le r6seau.
TABL. V.
List of shells o f A20. The sphere number, m, runs from 2 to 20. N(m) is the number o f points in shell m. P(m) the number o f classes and P P ( m ) the number o f subclasses.
N~4(m)
3 4 5
4 8 9
7l 17 8 I 30 9 I 33 I0 I 47 11 I 54 12 I 79 13 I 82 14 I 115 15 I 128 16 I 162 17 I 184 18 I 237 19 I 248
11527I 13047 23813 34285 43530 63713 87821 101331 I 141061 I 183243 I 213259 I 270766 I 337940 I 381342 I 485376 I 572017 I 646152 I
2222 VI.3.3.
196560 16773120 398034000 4629381120 34417656000 187489935360 81.4879774800 2975551488000 9486551299680 27052945920000 70486236999369 169931095326720 384163586352000 820166620815360 1668890090322000 3249631112232960 6096882661243920 11045500816896000 19428439855275360
Orbites.
C o m m e dans le cas du r6seau de Gosset, nous allons d6finir des classes d'6quivalence que nous appellerons orbites. N o u s dirons que les vecteurs y et z de A24(m) font partie de la m~me orbite si les valeurs absolues des composantes de ces vecteurs une fois arrang6es dans l'ordre d6croissant sont identiques. Par exemple : [4, 0, 0, 0, 0, 0, 0, - - 4, 0, 0, 0 . . . . . 0 ] ~ [0, 0, 0, 0, 0, 0, - - 4, - - 4, 0, 0 ..... 0]. Ne consid6rant pour l'instant que les valeurs absolues des composantes, nous caract6riserons une orbite donn6e par le plus grand vecteur, au sens lexicographique, que l ' o n obtient en o r d o n n a n t les valeurs absolues duns l'ordre d6croissant. Nous l'appellerons encore le directeur d'orbite biert que ce 12/20
169
vecteur n ' a p p a r t i e n n e pas forc6ment b. A24 . En effet, il se peut que ce directeur ne r6ponde pas aux exigences impos6es par le r6seau. Nous examinerons ces exigences plus loin en d6tail. Pour les premi6res sph6res, il y a b e a u c o u p de r6p6titions des valeurs des compo3antes, aussi il est c o m m o d e d'6crire les directeurs sous forme condens6e en dormant en exposant le nombre de r6p6titions. Par exemple, la plus petite sph6re, A24(2), se compose de 3 orbites qui sont iespectivement : (42, 022), (28, 0x6), (3, 123). Le tableau VI d o n n e les r6p6titions pour les directeurs d'orbites p o u r les sph6res j u s q u ' h m = 6. Ces directeurs sont dispos6s en deux colonnes. A gauche, les directeurs pairs qui font usage d'entiers pairs (E 2 L24 ) et/t droite les directeurs impairs. Barth [27] d o n n e cette table j u s q u ' h m = 20 ainsi q u ' u n algorithme p o u r la g6n6rer. Penchons-nous maintenant sur la question des contraintes. P o u r un mot du code de G o l a y ~24 les 24 positions peuvent se partitionner en deux ensembles. L'ensemble Fo des positions des ~t 0)) du m o t et l'ensemble F1 des positions occupfies par les <~1 >) du mot. Ainsi, si nous consid6rons le deuxi6me directeur pair de A24(2) nous avons huit ~t 2 )) qui occupent les positions FI d ' u n e des 759 octades. Par ailleurs, 7 des signes peuvent &re quelconques le huiti6me assurant la parit6. Cela nous fait doric un total de : 759 • 2 v ~ 97 152 vecteurs, dans cette otbite. Les contraintes impos6es sur le signe et la valeur des composantes d ' u n vecteur, y = [ y l , Y2 . . . . . Yi . . . . . Y24], de A24 peuvent se r6sumer c o m m e suit : (26a)
1. ]2y2 = 1 6 m 2. Ey~ = 4 n
;
p o s o n s p =ntmod2 I .
3. Yltmod2I = P 4. (Yitmod4j)]2 E ~24 La premi6re contrainte caract6rise l ' a p p a r t e n a n c e du vecteur ~t la sph6re m. Pour les trois autres contraintes, nous allons les interpr&er ~ l'aide de la figure suivante ofa les 24 composantes de y ont 6t6 repr6sent6es par leur d6composition binaire compl6ment deux. L a contrainte 3 indique que la parit6 de l'entier n d6termine la parit6 du vecteur (c'est4t-dire de toutes ses composantes). Ainsi, la colonne constitu6e des bits de rang 1 ne contient que des << 0>> p o u r un vecteur pair (p = 0) et que des ~ 1 ~> p o u r un impair (p = 1). L a contrainte 4 signifie que la c o l o n n e des bits de rang 2 doit constituer un m o t d u code de Golay. Enfin, la contrainte 2, qui peut aussi s'6crire (ZYi)tmodSff4 : P, dit que la somme des coordonn~es d ' u n vecteur pair est un multiple de 8, tandis qu'elle est un multiple de 8 plus 4 pour un impair. O n peut montrer facilement (les poids des mots de G o l a y 6tant multiples de 4) que la colonne des b i t s de rang 4 pr6sente une parit6 paire p o u r un vecteur pair et ANN. T[L~COMMUN.,41, n~ 3-4, 1986
J.-P. ADOUL. -- LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
170 TABL. VI.
-
-
Table des r6p6titions des directeurs des spheres Az4(m) pour m jusqu'~t 6.
Table of leaders of shells of A24 for m = 2 through 6. Pairs 10 8 6 4 1 2
(~)
1 2
(~)
Nombre de points
2
0
8
22 16
1104 97152
8 15 12 12
3108864 5275648
20 23 14 16 11 8
2
9 7 5 3
1
Nombre de points
1 23
98304
3 21 23
8290304 98304
170016 48 46632960 777216 126615552 24870912
5 19 1 2 21
174096384 24870912
|
3 8 13 435240960 1 1 7 15 24870912 2 12 10 1392771072 I 11 12 63307776 1 16 7 397934592
7 17 1 4 19 2 1 21 1 22
1417641984 870481920 24870912 2260992
|
6 2 4 1 2 2
9 15 5355536384 1 6 17 9923493888 2 3 19 1740963840 "3 21 8290304 3 20 174096384 1 22 2260992
1
(~)
4 1 2 1
1 2
Impairs
8 7 1 12 16
8 7 6 8 3 12 1 1 11 2 16 1 15 24
5 8
19 11
18 21 12 14 16 15 9 11 6 8
1
8614144 48576 2829066240 373063680 2720256 3108864 9285140480 1519386624 2785542144 397934592 8388608
i m p a i r e p o u r u n i m p a i r . L e s bits d e r a n g 8 o u s u p & r i e u r p e u v e n t p r e n d r e n ' i m p o r t e q u e l l e valeur.
figure 15 p o u r c h a q u e sph6re. L a figure 16 illustre le cas de la sph6re A24(3).
VI.3.4.
VI.3.5.
Propri6t6 de permutation.
C o m b i n a n t les c o n t r a i n t e s 3 et 4, ort p e u t les r6crire s o u s l a f o r m e suivartte q u i f a i t irttervenir la p a r t i t i o n d e s p o s i t i o n s s u i v a n t s les ~ 0 )) et les ~ 1 )) d u m o t de G o l a y : Fo et F I : (26 b)
YlImod4] = 2 -q- p
si i E Fa ,
Yltmod41 :
si i ~ Fo 9
p
Si l'on p e r m u t e les composantes du vecteur y l'intdrieur de Fo et F1 respectivement, le vecteur obtenu appartient encore dt A24 p u i s q u ' i l r 6 p o n d encore a u x c o n d i t i o n s n6cessaires et suffisantes. D e plus, le v e c t e u r o b t e n u a p p a r t i e n t t o u j o u r s h la m ~ m e sph6re e t ~ la m ~ m e o r b i t e et a v e c la m ~ m e p a r R & Nous allons exploiter cette propri6t6 importante pour construire l'algorithme de quantification optimal p o u r A24(m). P o u r cela, s u b d i v i s o n s c h a q u e o r b i t e e n sous-orbites : u n e s o u s - o r b i t e p o u r c h a q u e m o t p e r t i n e n t h cette o r b i t e , d u c o d e d e G o l a y . P o u r les o r b i t e s i m p a i r e s , t o u s les 4 096 m o t s d e G o l a y sont p e r t i n e n t s . P a r corttre, p o u r les o r b i t e s p a i r e s , seuls 1 o u 759 o u 2 576 m o t s s o n t p e r t i n e n t s suivartt q u e le d i r e c t e u r est c o m p a t i b l e a v e c les m o t s de p o i d s 0/24 o u 8/16 o u 12 r e s p e c t i v e m e n t . L e n o m b r e t o t a l de ces s o u s - o r b i t e s p e r t i n e n t e s , P P ( m ) , est i n d i q u 6 ~t la ANN. TI~LI~COMMUN.,41, n ~ 3-4, 1986
Classe d'6quivalence.
L a p r o p r i 6 t 6 de p e r m u t a t i o n n o u s p e r m e t de d~finir des classes d ' 6 q u i v a l e n c e q u i s o n t les s o u s - o r b i t e s . O n d i r a que y et z s o n t 6 q u i v a l e n t s si o n p e u t les r e n d r e 6gaux e n e f f e c t u a n t des p e r m u t a t i o n s de c o m p o s a n t e s d a n s F0 et F1 r e s p e c t i v e m e n t . VL3.6.
Algorithme (optimal) de quantification par A24(m).
Les c o m p o s a n t e s des d i r e c t e u r s p a i r s s o n t prises n o n n6gatives et a r r a n g 6 e s err o r d r e c r o i s s a n t en p l a ~ a n t les c o m p o s a n t e s de F1 a v a n t celles de F o . Les c o m p a s a n t e s des d i r e c t e u r s i m p a i r s s o n t avec le signe qui les r e n d c o n g r u e s ~t 1 [ m o d 4] et a r r a n g 6 e s dans l'ordre croissant. a) Prdparatifs. 1. O r d o n n e r les c o m p o s a n t e s de x p a r o r d r e de valeurs croissantes. Soit la constitution d'un tableau d ' i n d i c e s I ( j ) ; j = 1, 2 . . . . . 24. 2. O r d o n n e r x p a r o r d r e c r o i s s a n t des v a l e u r s a b s o l u e s de ses c o m p o s a n t e s . S o i t la c o n s t i t u t i o n d ' u n t a b l e a u d ' i n d i c e s I,,(j). 3. I n i t i a l i s e r P = 0, P & a n t l a p l u s g r a n d e p r o j e c t i o n r e n c o n t r 6 e j u s q u ' h pr6sent. 4. P o u r c h a q u e d i r e c t e u r p a i r , o n calcule S L P l a 13/20
J.-P. ADOUL. -- LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
(2L~,) Pairs
(2~, +u) Impairs
i
Poids . . . 16 8 4 2 1
2 z
...o o o ~ o , ~ ... o o o o o o =,=--tt,~ ...ooooo~iti~iol ... o o o o ~ o !oI!~!Iol
9" 23
Poids . . . 16 8 4 2 1
...o 0 ... o 0 "'" I
1 2 3 4 5 6
. . ,
...
Il~-t~-~
o 0 o 0 I
o 0 o 0 1
~ 0 o 0 1 I I l 1
o 0 o I 1
I ~ I l l II l 0 , 1I "I Q , 1I , I ~ itlloii~i 01ni111111 L'31 II I 1 ~11::ll I II II I l l l I I O,I,jOi,1, i.il-li-i l II I
. . . . . . . . . . . . . . . . .
... 0 0 0 0 0 0 : 0 ~ , I 0 ~
23 24
... o o o o o ,
P~'it~ paire J Hot du code de Golay
171
9. ,
0 0 0 0 0 0 ~r~r~lll I~ I~-'I I I I
9. .
II
Parit~ i m p a i r e - ~ Hot du code de Golag
t ~" I 0
II
I
I II II I 0 0 0 0 0 1 ,1,,I,,1, ~,J t.,ll L~
1' f I I
FIG. 15. - - Interpr6tation des contraintes impos~es sur les signes et valeurs des composantes d'un vecteur du r6seau de Leech. Les 24 composantes du vecteur sont repr6sent6es en binaire compl6ment b. deux.
Interpretation of the constraints on the values and signs of the components of Leech lattice points. The 24 components are written in two's complement binary representation. i
0rbitt~
1 "-". . . . . . . . . ,a . . . . . . . . .
Or'bites
1 ;; . . . . . . . . . ,A . . . . . . . . . . . . . . . . . . . . . . . .
i!
" "
iliL. Poids
(759)
~
.........................
il
!i
~
(2576)
..........
(759)
ii
...:~
i O'i~ ........... 8 ................ ~i~ ........................... 1 2 ......................... ~i~............. I 6 . . . . . ~'24i
FIG. 16. - - Illustration des PP(3) = 11527 sous-orbites (pertinentes) correspondant ~ la spla~re 3 (cf Table VI).
Illustration of the PP(3) = 11527 subclasses for shell m = 3 (cf Table VI). s o m m e des v a l e u r s a b s o l u e s de ses c o o r d o n n 6 e s ( SLP = •jy(j)).
:
b) Boucle sur les m o t s de Golay. P o u r le m o t d e c o d e e~(i = 0, 1. . . . . 4 095) auquel c o r r e s p o n d l a p a r t i t i o n F 1 , F 0 , faire : l) f o r m e r le t a b l e a u d ' i n d i c e s , Ion(j), qui p e r m e t d ' o r d o n n e r les v a l e u r s a b s o l u e s p a r o r d r e d 6 c r o i s s a n t m a i s en p l a ~ a n t les c o o r d o n n 6 e s de F1 a v a n t celle deFo;
c o r r e s p o n d a n t h F1 9 O n r 6 o r d o n n e a l o r s les c o m p o santes de ~ d a n s l ' o r d r e c r o i s s a n t , ce qui d o n n e n a i s s a n c e a u v e c t e u r d ' i n d i c e s Ibl(j) ; 5) p o u r c h a q u e directeur impair, y, faire : 5.1.) f o r m e r la s o m m e S = Y ' j [ ~ ( I b , ( J ) ) . Y(J)[, 5.2.) test : S > P ? o u i : P = S ; m 6 m o r i s e r ce leader, l ' i n d i c e i et le t a b l e a u Ib~ ; non : continuer. c) Extraction du vecteur quantifid ( d 6 c o d a g e ) .
2) calculer N , i le n o m b r e d e c o o r d o n n 6 e s n6gatives de x dans Ft ;
A p p e l o n s le v e c t e u r q u a n t i f i 6 Qo(x). Si le d i r e c t e u r r e t e n u y~ est :
3) p o u r c h a q u e directeur pair, y c o m p a t i b l e avec e~, faire :
1. P a i r :
3.1.) f o r m e r l a s o m m e S : Y,j l x ( I , , ( j ) ) . y ( j ) [ , 3.2.) si ( S >~ P ) et ( ( S L P = 0 [ m o d 8] et N,~ : 1 [ m o d 2]) o u (SLP---- 4 [ m o d 8] et N,I = 0 [ m o d 2])), a l o r s S : S - - 21x(Ia,(1)) . y(1)[. C e t t e o p 6 r a t i o n r e v i e n t ~t c a l c u l e r l'effet d ' i n v e r s e r le signe d e l a p l u s p e t i t e c o m p o s a n t e a p p a r t e n a n t /tF~, 3.3.) test : S > P ? o u i : P = S ; m 6 m o r i s e r ce directeur, l ' i n d i c e i et le t a b l e a u Io~ ; non : continuer. 4) f o r m e r le v e c t e u r ,~ q u i est une c o p i e d u v e c t e u r x d a n s laquelle o n a invers6 le signe des c o m p o s a n t e s 14/20
- - R e c l a s s e r les v a l e u r s d u d i r e c t e u r d a n s l ' o r d r e i n v e r s e d e celui d6fini p a r Ia,(j), s o i t : Q o ( x ( I o , ( j ) ) ) = y , ( j ) . --
Si la c o n d i t i o n 3.2. a 6t6 r e m p l i e , i n v e r s e r le signe p o u r j = 1. S o i t : Qo(x(/,,(1))) y,(1). -- Fin. 2. I m p a i r : - -
--
R e c l a s s e r les v a l e u r s d u d i r e c t e u r d a n s l ' o r d r e i n v e r s e d e celui d6fini p a r Ib,(j), s o i t : Q o ( x ( I a , ( j ) ) ) = y d j ) . C h a n g e r le signe des c o o r d o n n 6 e s d e F1 . Fin. ANN. T~LI~COMMUN.,41, n ~ 3-4, 1986
172
J.-P. ADOUL. -- LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
Remarques.
L ' a l g o r i t h m e peut &re acc616r6 par les techniques suivantes : 1) on peut faire la boucle sur la moiti6 des mots de Golay, soil, c~ avec i : 0, 1, 1. . . . . 2 047. En effet, si Ck est le c o m p l 6 m e n t (bit/~ bit) de c~, il est avantageux de traiter ces mots ensemble puisque les variables l b k , [ b k , X, N n k peuvent se d6duire assez simplement des variables correspondantes du m o t c~ ; 2) il est possible de calculer rapidement une borne sup6rieure p o u r la projection que peut atteindre une orbite donn6e. Ainsi, lorsque P, la plus grande valeur courante de la projection, d6passe cette borne, on peut 61iminer d ' e m b l 6 e cette orbite des calculs. L ' a l g o r i t h m e pr6c6dent est optimal en ce qu'il trouve le vecteur arrondi le plus proche. En fail, c o m m e nous le verrons bient6t, la probabilit6 est faible q u ' x soil tr6s proche d ' u n point de la sph6re ; au contraire, la situation est presque <~ connue>> d ' a v a n c e : il sera loin et entour6 d ' u n grand n o m b r e de voisins presqu'6quivalents. Aussi, p o u r l'applicalion pratique de la quantification vectorielle sph6rique, est-il int~ressant de d~velopper des algorithmes tr~s rapides m~me s'ils ne sont que sous-optimaux. Le probl6me de trouver le plus proche voisin sur une sph6re de A24 pr6sente quelques parall61es avec celui du d6codage << pond6r6 >> du code de Golay 6tendu [22].
VI.4. Quantification vectorielle sph~rique par r~seaux pour des distributions non uniformes. I1 est possible de concevoir un quantificateur vectoriel sph6rique 5. partir de r6seaux en choisissant des orbites b. bon escient. Voici deux m6thodes qui peuvent &re employ6es ; prenons l'exemple de Es : a) on p a r t de la sph6re la moins peupl6e, Es(1) de 240 points. On calcule alors la fr6quence normalis6e de chaque orbite. C'est-h-dire le n o m b r e de fois que cette orbite est invoqu6e divis6 par la cardinalit6 de l'orbite. L o r s q u ' u n e orbite, appelons-la A, pr6sente une forte fr6quence normalis6e, on r a j o u t e au quantificateur une orbite suppl6mentaire p r o v e n a n t d ' u n e sph6re de plus grand r a y o n (apr6s mise ~t l'6chelle) et telle que son directeur serait quantifi6 par le directeur de .4. On r6p6te la proc6dure en vue d'atteindre l'6quiprobabilit6 des fr6quences normalis6es et le d6bit requis ; b) la seconde m6thode consiste b, partir d ' u n e orbite tr6s peupl6e et b. atteindre les objectifs d'6quiprobabilit6 et de d6bit en r e t r a n c h a n t cette fois les orbites peu fr6quentes. U n e troisi6me m6thode int6ressante consiste quantifier en deux 6tapes. Par exemple, le vecteur coder peut ~tre compar6, dans une premi6re 6tape aux 240 points de E8(1). A chacun des 240 points, est associ6e une instruction indiquant sur quelle ANN. T~L~COMMUN., 41, n ~ 3-4, 1986
sph6re doit s'op6rer la quantification dans que ce point soit choisi ~t la premi6re heureusement, nous n ' a v o n s pas encore faqon simple de calculer les indices d ' u n cateur.
l'6ventualit6 6tape. Maltrouv6 une tel quantifi-
VII. PERFORMANCES DE LA QUANTIFICATION V E C T O R I E L L E SPHI~RIQUE PAR Rl~SEAU SUR LE BRUIT GAUSSIEN
Consid6rons une source d'6chantillons gaussiens ind6pendants, de m o y e n n e nulle et de variance unit6. Groupons-les par blocs de M 616ments p o u r former une s6quence de vecteurs de norme G e t d'orientation x. G 2 est une variable al6atoire distribu6e selon un chi-deux et par suite G se comporte c o m m e une variable gaussienne ( a p p r o x i m a t i o n de Fisher [23]) de moyenne G e t variance G2/(2 M 1). Nous avons vu en discutant la figure 7 que c'est en fait la valeur P G qui doit ~tre transmise. Or, P est une variable al6atoire qui peut se mod61iser convenablement par une loi 2 . La figure gaussienne de m o y e n n e P o e t de variance crv 17 montre l ' h i s t o g r a m m e obtenu pour P dans le codage utilisant A24(2).
Projection moyenne_~ Plus pet|te projection --'~ r~ ~ ORIGINE
~
1
~J~l I [ [ ~1~1~
0~50
I
0,7'5
to
FIG. 17. - - Histogramme de la projection P lorsque le quantificateur uti]ise la sphere 2 du r6seau de Leech. Histogram o f projection P when shell m = 2 is used as quantizer.
o,a
It 0,6 o F-
Plus petite projection 0~4
0 0,2 o,o
Ec~t
|
o,6 0;8
type
I
IjO
x Jo
I
1~2
"-
I
1~4
~
-
I
Ij6
-
_
I
Ij8
2jo
Fro. 1 8 . - Valeur moyenne et 6cart-type de la projection P ainsi que la plus petite projection trouv6e exp6rimentalement en fonction du d6bit par dimension lequel est 1i6 au num6ro de la sph/~re (cfi Table V). Mean value, standard deviation (• 10) o f the projection P and the minimal projection as a function of rate per dimension ( c f Table V).
15/20
J.-P. ADOUL. -- LA QUANTIFICATIONVECTORIELLEDE FORMES D'ONDES La figure 18 donne la valeur moyenne P 0 , l'6cart type % ainsi que la valeur minimale obtenue dans la quantification avec A24(m) en fonction de m. On peut 6crire P et G sous la forme suivante oh 80 et 8~ sont des variables gaussiennes centr6es ind6pendantes avec un 6cart-type fraction d'unit6 : (27)
P =Po[l
+ 80]
et
G = Go[1 + 8a].
N6gligeant le terme du second ordre, le produit P G a l e s caract6ristiques statistiques suivantes : (28)
E(PG) = P o G o , v a r ( P G ) l G 2 = a p2 + P 2 [ ( 2 M - -
1).
Plusieurs strat6gies peuvent s'envisager pour la transmission de l'information de la norme P G . a) P a s d e t r a n s m i s s i o n d e la n o r m e . Dans ce cas, la norme implicite au r6cepteur est celle donn6e par P o G o 9 L'erreur quadratique r6sultante du quantificateur sph6rique global (cf. Fig. 8) se d6compose en deux termes imputables respectivement ~t la quantification de l'orientation et de la norme. En effet, ~t chaque instant, on a : (29) (GE) 2 = (GEo) 2 + [ P G PoGo] 2.
consid6re un quantificateur de Max, on aura frO) = 1,
f(1) = 0,3634,
f(2) = 0,1175,
f(log23 = 1,584) = 0,1902.
On peut donc par une m&hode d'optimisation trouver le compromis qui minimise l'6quation (31) p o u r un d6bit global R = Ro + R e donn6. Les tableaux VII et V I I I d o n n e n t les performances obtenues par la quantification Es(m) d ' u n e part et A24(m ) d ' a u t r e part. Ces r6sultats sont repr6sent6s dans les courbes des figures 19, 20 et 21. L ' a n a l y s e a port6 sur 16 000 vecteurs al6atoires. D6s 2 500 vecteurs, t o u s l e s r6sultats avaient converg6 h l'int6rieur de la fourchette + 1 % du r6sultat final.
VIH. A P P L I C A T I O N A LA T R A N S M I S S I O N DE P A R O L E
b) T r a n s m i s s i o n d e la n o r m e p a r q u a n t i f i c a t i o n s c a l a i r e . Dans cette hypoth6se, on utilise un quantifi-
ffMR6)
:
(31)
E 2 = E2o + f f M R a )
var(eG),
oh R e est le d6bit par dimension. Pour achever le r6alisme, on s'en tiendra ~t un d6bit correspondant ~t un nombre entier de niveaux. Par exemple, si l'on
:
c) T r a n s m i s s i o n d e la n o r m e a u d d b i t o p t i m a l . Dans cette troisi6me hypoth6se, on suppose que l ' o n soit capable de transmettre la n o r m e darts les conditions optimales d6finies par la th6orie de la distorsion. Dans ce cas, le coefficient f ( M R ~ ) est donn6 par la relation : (32) f(MRa) = 2- 2M~.
Prenant l'esp6rance des deux termes apr6s normalisation, on obtient : (30) E 2 = Eo2 + var(PG).
cateur scalaire dont le r61e est de diminuer la contribution du 2 e terme de l'6quation (30) par un facteur
173
A BAS
DIgBIT
R6sumons bri6vement la probl6matique en transmission de parole ~t bas d6bit. L a technique de codage par pr6diction lin6aire (LPC) consiste h transmettre la parole ~t l'aide d ' u n filtre lin6aire mis ~t j o u r 50 100 fois par seconde. Ce filtre mod61ise l'6volution du conduit vocal. On peut lui associer une excitation
TABL.VII. - - Tableau des performances obtenues dans la quantification du bruit blanc gaussien par les sph6res de 1 jusqu'h 10 du r6seau de Gosset. E0 est l'erreur carr6e de quantification si l'on ne tient pas compte de la norme. E m est cette erreur carr6e quand la norme est transmise de far optimale au sens de la th6orie de l'information on donne alors le rapport R o I R en pour cent. Enfin E s est l'erreur carr6e quand on quantifie avec le meilleur quantificateur scalaire pour lequel on indique aussi R o . MSEperformances for quantization o f white gaussian noise with shells m = 1 through 10 o f the Gosset lattice. Eo is the MSEwhen the norm is not taken into consideration. E m corresponds to the case where the norm is quantized at rate distortion bound with the rate expressed in percent. Finally, E s is the MSE when the norm is scalar quantized.
Erreur quadratique totale n o
de la sphere
D6bit (bit)
eo
var(PG)
D6bit de I1--11
0,988 1,385 1,589 1,762 1,861 1,986 2,042 2,137 2,184 2,257
0,277 0,155 0,117 0,089 0,077 0,065 0,058 0,050 0,048 0,043
0,050 0,057 0,059 0,061 0,062 0,062 0,063 0,063 0,064 0,064
2,4 5,8 6,7 7,4 7,7 7,9 8,2 8,4 8,4 8,5
4
8 9 10
16/20
--
en %
D6bit de I1--11
e,
bit
0,325 0,198 0,155 0,123 0,107 0,093 0,084 0,074 0,071 0,064
1,58 1,58 1,58
1,58 1,58 2
e~ 0,352 0,208 0,162 0,130 0,114 0,099 0,090 0,079 0,076 0,069
ANN. T~L~COI~UN., 41, n ~ 3-4, 1986 5
174
J.-P. ADOUL. - LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
TABL. VIII. - - Tableau des performances obtenues dans la quantification du bruit blanc gaussien par des sph6res du r6seau de Leech. E0 est l'erreur carr6e de quantification si l ' o n ne tient pas compte de la norme. E m est cette erreur carr6e q u a n d la norme est transmise de fagon optimale au sens de la th6orie de l'information o n donne alors le rapport Ro] R en p o u r cent. Enfin E s est l'erreur carr6e quand on quantifie avec le meilleur quantificateur scalaire pour lequel o n indique aussi Ro. MSEperformances for quantization o f white gaussian noise with shells m = 1 through 10 o f the Leech lattice. E o is the MSE when the norm is not taken into consideration. E m corresponds to the case where the norm is quantized at rate distortion bound, with the rate expressed in percent. Finally, E s is the MSE when the norm is scalar quantized. Erreur quadratique totale n o
de la sph6re
D6bit (bit)
E0
var(PG)
11 13 16
0,733 1,000 1,190 1,338 1,458 1,560 1,649 1,727 1,859 1,970 2,106
0,402 0,275 0,211 0,171 0,144 0,126 0,109 0,099 0,081 0,070 0,057
0,013 0,016 0,017 0,018 0,018 0,019 0,019 0,019 0,020 0,020 0,020
=~ g o,so*
\.\\\ /" /
\ a \ \
/
'
(N0rme
bit
0,0
0,415 0,290 0,226 0,185 0,157 0,138 0,120 0,110 0,091 0,079 0,065
2,8 2,9
~
]
o iof,
== 0,25 1
~=*
o,,5
P
o.o5
\I,
0,415 0,291 0,228 0,186 0,157 0,138 0,120 0,110 0,091 0,079
0
1 1,58 1,58
Ouant. sceleire
~=
o) 0,05 t 0,00
D6bit de I1--11
en
0,9 1,6 2,0 2,2 2,3 2,5 2,6 2,7
L 9 P'='**"
=,
D6bit de I1-11
\f
0,065
.0o0 [ Ou=t soa88 ~ 0ptm
inferieu ,
0,60,O
Debit (btts/(Itm) , , , I
, : : 1,0 1~2 1,4 !,6 I,e 2,0 2~2 2:4
FIG. 19. - - Performances de la QVS b. p a r t i r des sph6res de E s p o u r du bruit blanc gaussien. Trois situations sont envisag6es : La n o r m e est transmise par quantification scalaire, par quantification optimale et enfin la n o r m e n ' e s t pas prise en consid6ration.
~
ebit
(blt
0)130 0,6 0,8 1,0 1,2 1,4 !~6 I;8 2:0 2~2 2j4 FIG. 20. - - Performances de la QVS ~. partir des sph6res de A~4 pour du bruit blanc gaussien. Trois situations sont envisag6es : la n o r m e est transmise p a r quantification scalaire, par quantification optimale (confondu avec le cas pr6c6dent) et enfin la n o r m e n ' e s t pas prise en consid6ration.
MSE performances o f SVQ using shells from the Gosset lattice. Three situations are recorded for the quantization o f the norm : scalar quantization optimal quantization and no quantization.
MSE performances o f SvQ using shells from the Leech lattice. Three situations are recorded for the quantization o f the norm : scalar quantization, optimal quantization and no quantization.
faite de bruit blanc ou d'impulsions p6riodiques /t la fr6quence du fondamental. Cette approche permet de transmettre/l un d6bit aussi bas que 800 bit/s. La parole ainsi g6n6r6e pr6sente une sonorit6 synth6tique et qui reste vuln6rable /L des erreurs de d6tection de fondamental ou de d6cision bruit blanc/impulsions (vois6/ non vois6) surtout lorsque la prise de son est faite en milieu bruyant. Pour obtenir une reproduction plus fid61e de la parole transmise, il n'y a pas d'autres solutions que de fournir plus d'information sur le signal d'excitation. Malheureusement, on ne sait pas encore transmettre
plus d'informations sur le signal d'excitation sans recourir ~ un d6bit beaucoup plus grand, disons 8 000 /L 10 000 bit/s. Ainsi, il existe au niveau des d6bits, un probl6me important. La conception d'une technique de transmission de parole/t un d6bit interm6diaire, disons 2 400 /t 9 600 bit/s, devra soigner /t la fois l'aspect mod61isation du r6sidu, l'aspect quantification et l'int6gration de ces deux aspects. Consid6rons le sch6ma de la figure 22. Le signal est d'abord analys6 puis filtr6 par le mod61e spectral inverse pour donner le r6siduel. C'est ce signal qu'il convient de transmettre le plus efficacement possible.
ANN. TI~LI~COMMUN., 41, n ~ 3-4, 1986
17/20
J.-P. ADOUL. -- LA QUANTIFICATIONVECTORIELLEDE FORMES D'ONDES
175
0.45 0.40
o
[
Q~nt. Seelaire
0.:3;~
Em]
I I_
0,
_1
~, o.25 o~
~ o.~ 0.15 0.10 g} 'L
0.05 0.~
Debit (bits/dim) :
:
:
:
:
:
'
FIG. 24. - - Empfitement du signal original, du r6sidu et du r6sidu apr6s r6duction de la r6solution B (RR) ou apr6s r6duction de la dimension (RD).
'
0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 2.2 2.4 FIG. 21. - - Comparaison des performances de Eset de A~, la norme 6tant transmise au d6bit optimal au sens de la th6orie de la distorsion. Comparison between Es and Az~ performances. The norm is quantized at the rate distortion bound.
.............
C01)AGE 0 U RF_glDU . . . . . . . . . . . . .
i
FIG. 22. - - SchBma en bloc d'un systBme de codage de parole pr6diction lin6aire et transmission du r6siduel. Pour coder ce dernier on op6re d'abord une r6duction de dimension (c'esth-dire du nombre d'6chantillons par seconde) suivi d'une quantification vectorielle. Block diagram o f a residual excited Lee vocoder. The residual is decimated then vector quantized.
Le premier obstacle b. une transmission 6conomique est que le r6siduel a u n ~ emp~tement~ (en bit) encore trop grand. Par ~ emp~ttement~, nous d6signons le produit de la r6solution, B (bit/6chantillon) par D, le n o m b r e de dimensions (ou d'6chantillons) par seconde c o m m e sugg6r6 par la figure 23. Apr6s passage dans un pr6dicteur lin6aire, le signal r6siduel pr6sente une structure simplifi6e, spectre blanc avec impulsions p6riodiques ou bruit blanc.
i
C'est
The product B D is expressed in bits per unit time and represents the <> o f the waveform. It is the rate necessary for uniform scalar quantization o f the waveform.
18/20
R
II1
Footprint ~ o f the original signal, the residual with reduced resolution (RR) or reduced dimensionality (rD).
Cependant, cette simplification ne se traduit pas imm6diatement en termes d ' u n emp~ttement tr6s r6duit. En effet, c o m m e l'illustre la figure 24, la dimension D1 du r6sidu reste inchang6e tandis que la r6solution B1 a 6t6 r6duite typiquement de 1 ~t 2 bit (soit 16g6rement moths que log2 du gain de pr6diction crs/trr puisque le r6sidu a m~me h6rit6 de pics plus prononc6s que dans le signal original). Conceptuellement, le probl6me peut s'6noncer c o m m e suit. L ' e m p ~ t e m e n t peut accueillir 2 al~ signaux distincts possibles. Cependant, les r6sidus de paroles ne repr6sentent q u ' u n minuscule sousensemble de ces possibilit6s. Si nous pouvons consacrer R bits au codage du r6sidu, il nous faut associer de la fa~on la plus correcte possible les 2 r 6tiquettes dont nous disposons ~t des signaux qui r e n d r o n t bien compte de ce sous-ensemble. D6s lors, trois directions essentielles s'offrent b. nous, qui ne sont d'ailleurs pas exclusives. Nous les n u m 6 r o t o n s 1, 2 et 3. La premi6re consiste ~ quantifier le r6sidu tel quel mats cette approche n'est envisageable que par quantification vectorielle statistique (vecteurs stock6s) ou par QVS non uniforme construite ~t partir de r6seaux. Les deux autres directions permettent d'appliquer directement la QVS uniforme p a r r6seau en op6rant au pr6alable une r6duction soit sur B
Y-,,
Ill,I,
..............................................................
8
(B~ pat
~.h.)
FIG. 23. - - Illustrations de l'empdtement d'une forme d'onde. Le produit B D se chiffre en bits. le d6bit qui est n6cessaire ~ la quantification scala/re uniforme de ce signal.
<<
:l.
,,,,,
,,
,I,,,,,,
,,,I,! ~..... i
,
'i,I, II Ir Ir 'U- " '1" ," . :....................................................................... !
I.
M~e
~
de dimensions ou
.I
d'~ntillcns par se~de (Largeur de bmde de fT~luer~e)
ANN. TI~L~COMMUN.,41, n ~ 3-4, 1986
176
J.-P. ADOUL.
soit sur D m o y e n n a n t la transmission en parall61e d ' u n e certaine information. L a figure montre l'emp~tement des signaux 1, 2 et 3 avant quantification. Direction 1. Codage du r6sidu directement p a r QVS
stock& Dans cette approche, nous utilisons la quantification vectorielle (sph6rique p a r 6conomie) avec vecteurs stock6s p o u r 6tiqueter le sous-ensemble des formes r6siduelles. C'est l ' a p p r o c h e 6tudi6e par Mabilleau [30]. Cette a p p r o c h e optimale a malheureusement p o u r inconv6nient la complexit6 des dictionnaires. Mabilleau a analys6 cette question sur processeur vectoriel csPI MAP-300 et obtenu des r6sultats de r a p p o r t signal h bruit p o u r signal r6siduel (ordre 8) de 8 000 6chantillons/s. L a figure 25 pr6sente ces 8.
rib
o'" ,- 6, z<[ rv
R~siduLPC Q~V~6
/
.o 5, ~" 4.
/
~/f
/ 0.0
/ Borne //sup~rieure
~ / Qv32 .
,.,"
02
,/d,.s,e /-
0.6
cos
Gaussien
/, 0.4
-
LA QUANTIFICATIONVECTORIELLE DE FORMES D'ONDES ment, d'autres m6thodes permettent d ' a p p r o c h e r ces r6sultats plus simplement. Direction 2. R6duction de la r6solution B e t codage Qvs par r6seau.
La technique standard p e r m e t t a n t de r~duire la r6solution B du r6sidu en retirant les impulsions est la pr6diction du fondamental. Pour cela, le signal r6siduel est trait6 p a r un filtre de la forme : H(z) = 1 - - ~ z - r , o/1 T e s t la p6riode du f o n d a m e n t a l en n o m b r e d'6chantillons. Les quantit6s ~ et T devant ~tre fournies p6riodiquement. La r6solution du signal r6sultant a diminu6 h nouveau d ' l ~ 2 bit, mais, ce qui est le plus important, ce signal est m a i n t e n a n t bien adapt6 ~t une QVS uniforme p a r r f s e a u (tout au moins pour un d~bit R sup6rieur /l 3/4 bit par 6chantillon). Direction 3. R6duction de la dimension D et codage QVS par r6seau.
4
7.
-
,?o, 0.e
1.0
1.2
FIO. 25. - - Performance de l'application directe de la quantification vectorielle stock6e au codage pleine bande du r6sidu de parole. Les limites technologiques ne permettent pas de d6passer des d6bits d'une petite fraction de bit par 6chantillon. On constate ccpendant qu'avec tr~s peu de d6bit, la pente des performances est tr6s forte r que ces performances se situent bi,'.n au-dessus de la limi e pour le bruit blanc ganssien indiquant que le r~sidu brut est charg6 de redondancc. Performance in dB obtained using (statistical) vector quanta zation on the speech residual. Current technology limits this approach to very low bit rates. One notes, however, that the slope is very steep and above the rate distorsion (upper) limit for white gaussian noise showing that the residual is still redundant.
r6sultats. On constate d ' a b o r d que les r6sultats sont bien au-dessus des p e r f o r m a n c e s optimales dans le cas du bruit blanc, un ph~nom~ne observ6 par d'autres auteurs [34]. Par ailleurs, p o u r les tailles de dictionnaires qu'il 6tait possible de consid6rer, les performances (pour des blocs de 32 6chantillons) croissent lin~airement avec le d6bit. A titre de curiosit6, on peut tenter de deviner ce que la poursuite de cette a p p r o c h e donnerait. En effet, dans l'hypoth6se o~ la performance reste lin6aire, une qualit6 de transmission c o m p a r a b l e a u meilleur codeur h 16 kbit serait possible, en principe avec de la QVS ( M = 32), avec un d~bit de 1 bit/6chantillon p o u r le r6sidu soit une transmission globale de la parole h 9 600 bit/s, cependant le dictionnaire devrait contenir quelque 4 milliards de vecteurs de dimension 32 ! HeureuseANN. T~LI~COMMUN.,41, n ~ 3-4, 1986
I1 existe toute une panoplie de techniques qui op~rent une r6duction du taux d'6chantillons D. Les plus courantes sont 9 9 bande de base d~cim6e, 9 impulsions multiples [31], 9 d6cimation g6n6ralisEe [35], 9 transmission d ' u n intervalle fondamental sur 2 [36], 9 transform6e de Fourier discr6te [37]. Une fois la dimension r6duite, le signal peut 8tre quantifi6 par Qvs uniforme. Codage dt m o y e n ddbit. Le probl6me du codage reste le m~me ~t m o y e n d6bit. L a Qvs par r6seau offre une grande souplesse dans le choix du d6bit du quantificateur. En effet, d ' u n e p a r t le d6bit peut 6tre un h o m b r e quelconque et n o n plus un entier c o m m e dans le cas scalaire. D ' a u t r e part, il est facile de varier ce d6bit avec le m~me algorithme en changeant simplement le num6ro de la sph6re (ou orbites) consid6r6e(s). Cette propri6t6 est particuli6rement int6ressante dans le cas d ' a p p r o c h e s par transform6e discr6te ou p a r sous-bandes.
IX.
CONCLUSION
La QV par l ' a p p r o c h e statistique qui met en oeuvre un dictionnaire de vecteurs arrondis permet un codage quasi optimal p o u r un d6bit donn& Cependant, les contraintes technologiques err mati6re de stockage et complexit6 de calcul limitent en pratique la taille des dictionnaires. Les r6seaux r6guliers de points rencontr6s dans le probl&me de l'empilement des spheres de m6me diam~tre peuvent &re employ6s p o u r sp6cifier un grand n o m b r e de points h partir d ' u n petit n o m b r e de vecteurs. Cela p e r m e t de franchir les 19/20
J.-P. ADOUL. -- LA QUANTIFICATION VECTORIELLE DE FORMES D'ONDES
177
L a q u a n t i f i c a t i o n v e c t o r i e l l e s p h d r i q u e est une f a g o n p r a t i q u e d e t i r e r p a r t i d e s r6seaux rdguliers. Elle p e r m e t n o t a m m e n t en 8 d i m e n s i o n s de c o n c e v o i r des q u a n t i f i c a t e u r s /t d 6 b i t a j u s t a b l e de fagon quasi c o n t i n u e au-del/l d ' u n b i t p a r d i m e n s i o n . Le g a i n de ces q u a n t i f i c a t e u r s e n t e r m e de r a p p o r t signal /t b r u i t est m a l h e u r e u s e m e n t m o d e s t e et leur usage n ' e s t indiqu6 q u e l o r s q u e le d 6 b i t a u q u e l o n op6re est tel q u ' u n gain d e 1 /t 3 d B se r 6 p e r c u t e d i r e c t e m e n t s u r les p e r f o r m a n c e s s u b j e c t i v e s c o m m e c ' e s t le cas p o u r le c o d a g e d u r6sidu d e p a r o l e e n t r e 2 000 et 4 000 bit/s.
en quelque sorte deux approches extremes au probl6me de repr6senter un grand nombre de vecteurs : l'une r e v i e n t h t o u t m 6 m o r i s e r t a n d i s q u e l ' a u t r e use d ' u n m a x i m u m de << rdcursivitd~> d a n s la g d n 6 r a t i o n d e ces vecteurs. E n fait, u n e c o m b i n a i s o n d e ces a p p r o c h e s s e m b l e & r e la v o i e vers les q u a n t i f i c a t e u r s les p l u s p e r f o r m a n t s /t l ' i n t d r i e u r d e s l i m i t e s t e c h n o l o g i q u e s . O n p e u t s o n g e r d ' a b o r d b. m e t t r e en c a s c a d e u n q u a n t i f i c a t e u r s t a t i s t i q u e et u n QVS p a r rdseau, le s e c o n d a y a n t p o u r r61e d e q u a n t i f i e r le v e c t e u r d e l ' e r r e u r c o m m i s e p a r le p r e m i e r . M a i s il s e m b l e e n c o r e p l u s i n t d r e s s a n t d e c o n c e v o i r des a l g o r i t h m e s conduisant directement au quantificateur hybride qui p o u r spdcifier les v e c t e u r s , c o m b i n e r a a d r o i t e m e n t m d m o r i s a t i o n et r6cursivit6.
Les a p p r o c h e s s t a t i s t i q u e et a l g 6 b r i q u e ne s o n t p a s en c o m p d t i t i o n . Bien a u c o n t r a i r e , elles r e p r d s e n t e n t
M a n u s c r i t recu le 10 m a i 1985, acceptd le 28 janvier 1986.
limites t e c h n o l o g i q u e s des q u a n t i f i c a t e u r s statistiques c e p e n d a n t le revers d e l a m 6 d a i l l e c ' e s t que l e s nouveaux types de quantificateurs ne s'appliquent qu'~t des s i t u a t i o n s d e r d p a r t i t i o n u n i f o r m e .
BIBLIOGRAPHIE [1] ADOUL (J. P.). Speech coding algorithms and vector quantization. Chapter 3 of <>. K. Feher editor, PrenticeHall, NJ (1986). [2] MAX (.r.). Quantizing for minimum distortion. I R E Trans. IT, USA (mars 1960), 6, pp. 16-21. [3] PAEZ (M. D.) and GLISSON (T. H.). Minimum mean squared error quantization in speech PCM and DPCM systems. IEEE Trans. COM., USA (avr. 1972), pp. 225-230. [4] NEWMAN (D. J.). The hexagon theorem. IEEE Trans. IT, USA (mars 1984), 30, pp. 137-139. [5] BARNES(E. S.) and SLOANE (N. J. A.). The optimal lattice quantizer in three dimensions. Algebraic discrete methods, S l A M rev., USA (mars 1983), 4, n ~ 1, pp. 30-41. [6] MEYER (L. S.). Data analysis for scientists and engineers. Wiley, New York (1975). [7] SLOANe (N. J. A.). Les empilements de sph6res. Pour la science, Fr (mars 1984), pp. 44-55. [8] LeeCH (J.) and SLOANE (N. J. A.). Sphere packing and error-correcting codes. Canad. J. Math. (1971), 23, pp. 718745. [9] SLOANE(N. J. A.). Tables of sphere packings and spherical codes. IEEE Trans. IT, LISA (1981), 27, pp. 327-338. [10] DE BtrDA (P.). Encoding and decoding algorithms for an optimal lattice based code. 1EEE, Int'l Communication Conf., Denver (1981). [11] FORNEY (G. D.) et aL Efficient modulation for bandlimited channels. IEEE Selected Areas in Communications (sep. 1984), 2, n ~ 5, pp. 632-647. [12] G~RSHO (A.). Asymptotically optimal block quantization. 1EEE Trans. IT, USA (1979), 25, pp. 373-380. [13] CONWA'/ (J. H.) and SLOANE (N. J. A.). Voronoi regions of lattices. Second moments of polytopes and quantization. 1EEE Trans. IT, LISA (1982), 28, pp. 211-226. [14] CONWAu (J. H.) and SLOANe (N. J. A.). On the Voronoi regions of certain lattices. S I A M J. Algebraic Discrete Methods (1984), 5, pp. 294-305. [15] CONWAY (J. H.) and SLOANE (N. J. A.). Fast quantizing and decoding algorithms for lattice quantizers and codes. 1EEE Trans. IT, USA (1982), 28, pp. 227-232. [16] SLePXAN (D.). Permutation modulation. Proc. IEEE, USA (1965), 53, pp. 228-236. [17] BERGrR (T.), JeLINEK (F.) and WOLF (J. K.). Permutation codes for sources. IEEE Trans. IT, USA (1972), 18, pp. 160169. [18] LEECH (J.). Notes on sphere packings. Canad. J. Math. (1967), 19, pp. 251-267. [19] CONWAu O.H.). A caracterisation of Leech's lattice. Inventiones math., GB (1969), 7, pp. 137-142. [20] CONWAY (J. H.), PARKER (R. A.) and SLOANE (N. J. A.). The covering radius of the Leech lattice. Proc. Royal Soc. London (1982), A 380, pp. 261-290. [21] WOLFMANN(J.). A permutation decoding of the (24, 12, 8) 20/20
Golay code. IEEE Trans. IT, USA (1983), 29, pp. 748750. [22] BATrAIL(G.). D6codage ponddr6 optimal des codes iin6aires en blocs. Ann. T~ldcommun., Fr (1983), 37, n ~ 11-12, pp. 443-459. [23] CONWAY (J. H.) and SLOANE (N. J. A.). Fast encoding method for lattice codes and quantizers. 1EEE Trans. IT, USA (1983), 29, pp. 820-824. [24] MACWILLIAMS(F. J.) and SLOANe (N. J. A.). The theory of error-correcting codes. North-Holland, Amsterdam (1977). [25] GeRSHO (A.). On the structure of vector quantizers. IEEE Trans. 1T, LISA (1982), 28, pp. 157-166. [26] LAMBLIN (C.). Codage vectoriel /t bas debit. Rapport de stage E N S T Bretagne, F r (1983). [27] BARrH (M.). Codage et quantification de la parole en vue d'une transmission/t 2 400 bit/s. Universit~ de Sherbrooke, Canada (singe ENST) (oct. 1983). [28] BARTH (M.). Implantation sur circuit int6grd d'un algorithme de quantification vectorielle. Projet de fin d'6tude, ENST, Paris (juin 1984). [29] ADOUL (J. P.), LAMBLIN (C.) and LeGUVADeR CA.). Base band speech coding at 2 400 bit/s using spherical vector quantization. ICASSP-84, IEEE, USA, pp. 1.12.1-1.12.4. [30] MAmLLeAU (Ph.). La quantification vectorielle et son application au codage de la parole. Th6se de P h . D . , Universit~ de Sherbrooke, Canada (sep. 1983). [31] ATAL (B.), R~MDE (J.). A new model of LPC excitation for producing natural sounding speech at low bit rate. 1CASSP82, pp. 614-617. [32] GERSrIO (A.), CUPERMAN (C.). Vector quantization : a pattern-matching technique for speech coding. IEEE Communications Magazine, USA (d6c. 1983). [33] GRAY (R. M.). Vector quantization. IEEE A S S P Magazine (avr. 1984). [34] ABUT (H.) et al. Vector quantization of speech and speech like waveforms. IEEE A S S P (juin 1982), 30, n ~ 3, pp. 423435. [35] ADOUL (J. P.), DIDELOT (F.), MABILLeAU(P.), MomssEr'rE (S.). Generalization of the multipulse coding for low bit rate coding purposes : the generalized decimation. I E g E ICASSP 0985). [36] MALAH (D.). Time domain algorithms for harmonic bandwidth reduction and time scaling of speech signals. 1EEE Trans. ASSP, LISA (avr. 1979), 27, n ~ 2, pp. 121133. [37] KAa'~RFELD (H.). A DFT-based residual-excited linear predictive coder (gELp) for 4.8 and 9.6 Kb/s. IEEEICASSP1981, pp. 824-827. [38] PEPXN (G.). Codage num6rique de la parole utilisant le Tons et la quantification vectorielle sph6rique. M6moire de maitrise. Univ. Sherbrooke, Canada (d6c. 1984). [39] SCHALKWlJK (J. P. N.). An algorithm for source coding. 1EEE Trans. IT, LISA (mai 1972), 18, n ~ 3, pp. 395-399.
AsN. TI~L~COMMUN.,41, n ~ 3-4, 1986