Documentation

# lloyds

Optimize quantization parameters using Lloyd algorithm

## Syntax

```[partition,codebook] = lloyds(training_set,initcodebook) [partition,codebook] = lloyds(training_set,len) [partition,codebook] = lloyds(training_set,...,tol) [partition,codebook,distor] = lloyds(...) [partition,codebook,distor,reldistor] = lloyds(...) ```

## Description

`[partition,codebook] = lloyds(training_set,initcodebook) ` optimizes the scalar quantization parameters `partition` and `codebook` for the training data in the vector `training_set`. `initcodebook`, a vector of length at least 2, is the initial guess of the codebook values. The output `codebook` is a vector of the same length as `initcodebook`. The output `partition` is a vector whose length is one less than the length of `codebook`.

See Represent Partitions, Represent Codebooks, or the reference page for `quantiz` in this chapter, for a description of the formats of `partition` and `codebook`.

### Note

`lloyds` optimizes for the data in `training_set`. For best results, `training_set` should be similar to the data that you plan to quantize.

`[partition,codebook] = lloyds(training_set,len)` is the same as the first syntax, except that the scalar argument `len` indicates the size of the vector `codebook`. This syntax does not include an initial codebook guess.

`[partition,codebook] = lloyds(training_set,...,tol)` is the same as the two syntaxes above, except that `tol` replaces 10-7 in condition 1 of the algorithm description below.

`[partition,codebook,distor] = lloyds(...)` returns the final mean square distortion in the variable `distor`.

```[partition,codebook,distor,reldistor] = lloyds(...)``` returns a value `reldistor` that is related to the algorithm's termination. In condition 1 of the algorithm below, `reldistor` is the relative change in distortion between the last two iterations. In condition 2, `reldistor` is the same as `distor`.

## Examples

The code below optimizes the quantization parameters for a sinusoidal transmission via a three-bit channel. Because the typical data is sinusoidal, `training_set` is a sampled sine wave. Because the channel can transmit three bits at a time, `lloyds` prepares a codebook of length 23.

```% Generate a complete period of a sinusoidal signal. x = sin([0:1000]*pi/500); [partition,codebook] = lloyds(x,2^3)```

The output is below.

```partition = Columns 1 through 6 -0.8540 -0.5973 -0.3017 0.0031 0.3077 0.6023 Column 7 0.8572 codebook = Columns 1 through 6 -0.9504 -0.7330 -0.4519 -0.1481 0.1558 0.4575 Columns 7 through 8 0.7372 0.9515 ```

## Algorithms

`lloyds` uses an iterative process to try to minimize the mean square distortion. The optimization processing ends when either

• The relative change in distortion between iterations is less than 10-7.

• The distortion is less than `eps*max(training_set)`, where `eps` is the MATLAB floating-point relative accuracy.

## References

[1] Lloyd, S.P., “Least Squares Quantization in PCM,” IEEE Transactions on Information Theory, Vol. IT-28, March, 1982, pp. 129–137.

[2] Max, J., “Quantizing for Minimum Distortion,” IRE Transactions on Information Theory, Vol. IT-6, March, 1960, pp. 7–12.