lloyd.3

speech signal process tools

.\" Copyright (c) 1987-1990 Entropic Speech, Inc.
.\" Copyright (c) 1997 Entropic Research Laboratory, Inc. All rights reserved.
.\" @(#)lloyd.3	1.4 18 Apr 1997 ESI/ERL
.ds ]W (c) 1997 Entropic Research Laboratory, Inc.
.TH LLOYD 3\-ESPSsp 18 Apr 1997
.SH NAME
lloyd \- generate scalar quantizer using Lloyd's algorithm
.SH SYNOPSIS
.ft B
lloyd (data, n, cbk, ncwds, converg, hstrm, final_dist, cbk_dist, pop)
.br
double data[], cbk[], converg, final_dist, cbk_dist[];
.br
long n, pop[];
unsigned ncwds;
.br
FILE *hstrm;
.SH DESCRIPTION
This routine generates a locally optimal scalar quantizer codebook 
(
.I cbk
) by using
Lloyd's algorithm.
It
returns the codebook
along with the final distortion 
(
.I final_dist
) that results from representing the training data
(
.I data
)
by the codebook, 
the number of 
.I data
elements that were closest to each codebook element
(
.I pop
), 
and the average distortion ( mean squared error) 
associated with each codebook element
(
.I cbk_dist
). 
The user inputs an array of training data 
(
.I data
) and the number of elements in it
(
.I n
),
specifies how many codewords 
(
.I ncwds
) are to be generated to represent the
training data, and also a convergence threshold
(
.I converg
).
.PP
.I lloyd
starts by computing the mean of all the elements in
.IR data 
to form the codebook of length one.  Larger codebooks are then
generated by splitting the previous codebook (replacing each
codeword by two codewords, separated by a small number), and
going through a process of improving the codebook until convergence
is reached.  This process works as follows:
.PP
The squared distance is computed between every element of
.I data
and every codeword.  Each codeword is then replaced by the mean
of all the elements of
.I data
for which that codeword is the nearest neighbor.  The mean square
error that results when each element of
.I data
is replaced by the nearest element in the codebook is computed.
The improvement loop stops when the difference between the old
distortion and the new distortion, divided by the old distortion,
becomes less than
.IR converg .
.PP
It is possible for an
"empty cell"
to appear.  This happens when no element of
.I data
has a particular codebook element as its nearest neighbor.
Empty cells are handled by splitting the codeword corresponding
to the largest cluster (the codeword with the most training elements
as nearest neighbors); this is a heuristic.
.PP
If the argument
.I hstrm
is non-null, it represents a file descriptor and history information
is written on it.
.PP
The output codebook is sorted in increasing order.
.SH DIAGNOSTICS
If more than 10 empty cells appear a message is written to
.I stderr
and the program exits.  This should never occur unless
.I ncwds
is too large compared to
.IR n .
.SH BUGS
None known.
.SH REFERENCES
Y. Linde, A. Buzo, R.M. Gray,
An Algorithm for Vector Quantizer Design
IEEE Transactions on Communications,
Vol. COM-28, No. 1, January, 1980
.SH AUTHOR
Joseph T. Buck, modifications by David K. Burton