Added bit-allocation table
[speexdsp.git] / doc / manual.lyx
1 #LyX 1.2 created this file. For more info see http://www.lyx.org/
2 \lyxformat 220
3 \textclass article
4 \language english
5 \inputencoding auto
6 \fontscheme default
7 \graphics default
8 \paperfontsize default
9 \spacing single 
10 \papersize Default
11 \paperpackage a4
12 \use_geometry 0
13 \use_amsmath 0
14 \use_natbib 0
15 \use_numerical_citations 0
16 \paperorientation portrait
17 \secnumdepth 3
18 \tocdepth 3
19 \paragraph_separation indent
20 \defskip medskip
21 \quotes_language english
22 \quotes_times 2
23 \papercolumns 1
24 \papersides 1
25 \paperpagestyle headings
26
27 \layout Title
28
29 The Speex Codec Manual
30 \newline 
31 (draft)
32 \layout Author
33
34 Jean-Marc Valin
35 \layout Standard
36 \pagebreak_top 
37 Copyright (c) 2002 Jean-Marc Valin.
38 \layout Standard
39
40 Permission is granted to copy, distribute and/or modify this document under
41  the terms of the GNU Free Documentation License, Version 1.1 or any later
42  version published by the Free Software Foundation; with no Invariant Section,
43  with no Front-Cover Texts, and with no Back-Cover.
44  A copy of the license is included in the section entitled "GNU Free Documentati
45 on License".
46  
47 \layout Section*
48
49 Disclaimer
50 \layout Standard
51
52 This document is meant to provide useful information on the Speex codec
53  but there is absolutely no warranty regarding usefulness or correctness
54  of the information provided.
55  Also, some techniques used in Speex are said to be 
56 \begin_inset Quotes eld
57 \end_inset 
58
59 similar
60 \begin_inset Quotes erd
61 \end_inset 
62
63  to techniques used in known codecs.
64  This should not be understood as an acknowledgment that Speex is using
65  any patented algorithm used in these codecs, but merely that comprehension
66  of Speex can be facilitated by thinking that the principles of operation
67  are the same or similar.
68  Of course, there's also the obligatory 
69 \begin_inset Quotes eld
70 \end_inset 
71
72 all trademarks are property of their respective owner
73 \begin_inset Quotes erd
74 \end_inset 
75
76 .
77 \layout Standard
78 \pagebreak_top \pagebreak_bottom 
79
80 \begin_inset LatexCommand \tableofcontents{}
81
82 \end_inset 
83
84
85 \layout Section
86
87 Introduction to Speex
88 \layout Standard
89
90 Speex has been designed with the following goals in mind:
91 \layout Itemize
92
93 No use of patented algorithms (implies that we can't use patented algorithms
94  such as ACELP)
95 \layout Itemize
96
97 Good for Voice over IP (VoIP)
98 \layout Itemize
99
100 Provide very good quality speech (at least as an option)
101 \layout Itemize
102
103 Allow a wide range of quality/bit-rate
104 \layout Itemize
105
106 Integrate both narrowband and wideband coding
107 \layout Itemize
108
109 Reasonable complexity
110 \layout Standard
111
112 Throughout the design the following assumptions and constraints were considered
113 \layout Itemize
114
115 Presence of packet losses
116 \layout Itemize
117
118 Integrity of received frames (no bit-errors)
119 \layout Itemize
120
121 Memory footprint is neither critical nor unlimited
122 \layout Standard
123
124 This led us to choose the CELP technique for Speex.
125  Also many design decisions were based on the original goals and assumptions:
126 \layout Itemize
127
128 Minimizing the amount of information extracted from past frames (for robustness
129  to packet loss)
130 \layout Itemize
131
132 Dynamically-selectable codebooks (LSP, pitch and innovation)
133 \layout Itemize
134
135 G.728-like fixed codebooks (without backward-adaptive grains) because of
136  patent issues
137 \layout Section
138
139 Introduction to CELP Coding
140 \layout Standard
141
142 Speex is based on the CELP, which stands for Code Excited Linear Prediction.
143  This section attempts to introduce the principles behind CELP, so if you
144  are already familiar with CELP, you can safely skip to section 
145 \begin_inset LatexCommand \ref{sec:Speex-narrowband-mode}
146
147 \end_inset 
148
149 .
150  The CELP technique is based on three ideas:
151 \layout Enumerate
152
153 The use of a linear prediction (LP) model to model the vocal tract
154 \layout Enumerate
155
156 The use of (adaptive and fixed) codebook entries as input (excitation) of
157  the LP model
158 \layout Enumerate
159
160 The search performed in closed-loop in a 
161 \begin_inset Quotes eld
162 \end_inset 
163
164 perceptually weighted domain
165 \begin_inset Quotes erd
166 \end_inset 
167
168
169 \layout Subsection
170
171 Linear Prediction
172 \layout Standard
173
174 The linear prediction model represents each speech sample as linear combination
175  of past samples, plus an error signal called the excitation (or residual).
176 \begin_inset Formula \[
177 x(n)=\sum _{i=1}^{N}a_{i}x(n-i)+e(n)\]
178
179 \end_inset 
180
181
182 \layout Standard
183
184 In the 
185 \emph on 
186 z
187 \emph default 
188 -domain, this can be expressed as
189 \layout Standard
190
191
192 \begin_inset Formula \[
193 x(z)=\frac{1}{A(z)}\: e(z)\]
194
195 \end_inset 
196
197
198 \layout Standard
199
200 where 
201 \begin_inset Formula $A(z)$
202 \end_inset 
203
204  is defined as
205 \layout Standard
206
207
208 \begin_inset Formula \[
209 A(z)=1-\sum _{i=1}^{N}a_{i}z^{-i}\]
210
211 \end_inset 
212
213
214 \layout Standard
215
216 We usually refer to 
217 \begin_inset Formula $A(z)$
218 \end_inset 
219
220  as the analysis filter and 
221 \begin_inset Formula $1/A(z)$
222 \end_inset 
223
224  as the synthesis filter.
225 \layout Standard
226
227 The 
228 \begin_inset Formula $A(z)$
229 \end_inset 
230
231  filter is computed using the Levinson-Durbin algorithm, which starts from
232  the auto-correlation 
233 \begin_inset Formula $R(m)$
234 \end_inset 
235
236  of the signal 
237 \begin_inset Formula $x(n)$
238 \end_inset 
239
240 .
241 \layout Standard
242
243
244 \begin_inset Formula \[
245 r(m)=\sum _{i=0}^{N-1}x(i)x(i-m)\]
246
247 \end_inset 
248
249
250 \layout Standard
251
252 For an order 
253 \begin_inset Formula $N$
254 \end_inset 
255
256  filter, we have:
257 \begin_inset Formula \[
258 \mathbf{R}=\left[\begin{array}{cccc}
259  r(0) & r(1) & \cdots  & r(N-1)\\
260  r(1) & r(0) & \cdots  & r(N-2)\\
261  \vdots  & \vdots  & \ddots  & \vdots \\
262  r(N-1) & r(N-2) & \cdots  & r(0)\end{array}
263 \right]\]
264
265 \end_inset 
266
267
268 \begin_inset Formula \[
269 \mathbf{r}=\left[\begin{array}{c}
270  r(1)\\
271  r(2)\\
272  \vdots \\
273  R(N)\end{array}
274 \right]\]
275
276 \end_inset 
277
278
279 \layout Standard
280
281 The filter coefficients 
282 \begin_inset Formula $a_{i}$
283 \end_inset 
284
285  are found by solving the system 
286 \begin_inset Formula $\mathbf{Ra}=\mathbf{r}$
287 \end_inset 
288
289 .
290  What the Levinson-Durbin algorithm does here is making the solution to
291  the problem 
292 \begin_inset Formula $\mathcal{O}\left(N^{2}\right)$
293 \end_inset 
294
295  instead of 
296 \begin_inset Formula $\mathcal{O}\left(N^{3}\right)$
297 \end_inset 
298
299  by exploiting the fact that matrix 
300 \begin_inset Formula $\mathbf{R}$
301 \end_inset 
302
303  is toeplitz hermitian.
304  Also, it can be proved that all the roots of 
305 \begin_inset Formula $A(z)$
306 \end_inset 
307
308  are withing the unit circle, which means that 
309 \begin_inset Formula $1/A(z)$
310 \end_inset 
311
312  is always stable.
313  This is in theory; in practice because of finite precision, there are two
314  commonly used techniques to make sure we have a stable filter.
315  First, we multiply 
316 \begin_inset Formula $r(0)$
317 \end_inset 
318
319  by a number slightly above one (such as 1.0001), which is equivalent to
320  adding noise to the signal.
321  Also, we can apply a window the the auto-correlation, which is equivalent
322  to filtering in the frequency domain, reducing sharp resonances.
323 \layout Subsection
324
325 Pitch Prediction
326 \layout Standard
327
328 During voiced segments, the speech signal is very periodic, so it is possible
329  to take advantage of that.
330 \layout Standard
331
332
333 \begin_inset Formula \[
334 e(n)=\beta e(n-T)+c(n)\]
335
336 \end_inset 
337
338
339 \layout Standard
340
341 where 
342 \begin_inset Formula $T$
343 \end_inset 
344
345  is the pitch period and 
346 \begin_inset Formula $\beta $
347 \end_inset 
348
349  is the pitch gain.
350  In the 
351 \emph on 
352 z
353 \emph default 
354 -domain, the excitation can be expressed as:
355 \layout Standard
356
357
358 \begin_inset Formula \[
359 e(z)=\frac{1}{1-\beta z^{-T}}\: c(z)\]
360
361 \end_inset 
362
363 where 
364 \begin_inset Formula $c(n)$
365 \end_inset 
366
367  is taken from the 
368 \emph on 
369 innovation codebook
370 \emph default 
371 .
372 \layout Subsection
373
374 Innovation Codebook
375 \layout Standard
376
377 This is where most of the bits in a CELP codec are allocated.
378  It represents the information that couldn't be obtained either from linear
379  prediction or pitch prediction.
380 \layout Subsection
381
382 Analysis-by-Synthesis and Error Weighting
383 \layout Standard
384
385 Most (if not all) modern audio codecs attempt to 
386 \emph on 
387 shape
388 \emph default 
389  the noise so that it is the hardest to detect with the ear.
390  That means that more noise can be tolerated in parts of the spectrum that
391  are louder and 
392 \emph on 
393 vice versa
394 \emph default 
395 .
396  That's why the error is minimized for the perceptually weighted signal
397 \begin_inset Formula \[
398 X_{w}(z)=W(z)X(z)\]
399
400 \end_inset 
401
402 where 
403 \begin_inset Formula $W(z)$
404 \end_inset 
405
406  is the weighting filter, usually of the form
407 \layout Standard
408
409
410 \begin_inset Formula \begin{equation}
411 W(z)=\frac{A\left(\frac{z}{\gamma _{1}}\right)}{A\left(\frac{z}{\gamma _{2}}\right)}\label{eq:weighting_filter}\end{equation}
412
413 \end_inset 
414
415
416 \layout Section
417
418 Speex narrowband mode
419 \begin_inset LatexCommand \label{sec:Speex-narrowband-mode}
420
421 \end_inset 
422
423
424 \layout Standard
425
426 This section looks at how Speex works for narrowband (
427 \begin_inset Formula $8\: \mathrm{kHz}$
428 \end_inset 
429
430  sampling rate) operation.
431  The frame size for this mode is 
432 \begin_inset Formula $20\: \mathrm{ms}$
433 \end_inset 
434
435 , corresponding to 160 samples.
436  Each frame is also subdivided into 4 sub-frames of 40 samples each.
437 \layout Subsection
438
439 LPC Analysis
440 \layout Standard
441
442 An LPC analysis is first performed on a (Hamming) window that spans all
443  the current frame and half a frame in advance.
444  The LPC coefficients are then converted to Line Spectral Pair (LSP), a
445  representation that is more robust to quantization.
446  The LSP's are quantized using 30 bits for higher quality modes and 18 bits
447  for lower quality.
448  The quantized LSP's are considered to be associated to the 
449 \begin_inset Formula $4^{th}$
450 \end_inset 
451
452  sub-frames and the LSP's associated to the first 3 sub-frames are linearly
453  interpolated using the current and previous LSP's.
454 \layout Standard
455
456 The perceptual weighting filter 
457 \begin_inset Formula $W(z)$
458 \end_inset 
459
460  used by Speex corresponds to the one described by eq.
461  
462 \begin_inset LatexCommand \ref{eq:weighting_filter}
463
464 \end_inset 
465
466  with 
467 \begin_inset Formula $\gamma _{1}=0.9$
468 \end_inset 
469
470  and 
471 \begin_inset Formula $\gamma _{2}=0.6$
472 \end_inset 
473
474 .
475  We can use the unquantized 
476 \begin_inset Formula $A(z)$
477 \end_inset 
478
479  filter since the weighting filter is only used in the encoder.
480 \layout Subsection
481
482 Pitch Prediction (adaptive codebook)
483 \layout Standard
484
485 Speex uses a 3-tap prediction for pitch.
486  That is, 
487 \layout Standard
488
489
490 \begin_inset Formula \[
491 e(n)=\beta _{0}e(n-T-1)+\beta _{1}e(n-T)+\beta _{2}e(n-T+1)+c(n)\]
492
493 \end_inset 
494
495
496 \layout Standard
497
498 where 
499 \begin_inset Formula $T$
500 \end_inset 
501
502  is the pitch period and the 
503 \begin_inset Formula $\beta _{i}$
504 \end_inset 
505
506  are the prediction (filter) taps.
507  The period and quantized gains are determined in closed loop.
508 \layout Subsection
509
510 Innovation Codebook
511 \layout Standard
512
513 In Speex, the innovation signal is quantized using shape-only vector quantizatio
514 n (VQ).
515  That means that the codebooks that are used represent both the shape and
516  the gain at the same time.
517  This save many bits that would otherwise be allocated for a separate gain
518  at the price of a slight increase in complexity.
519  Except for the absence of (backward-adaptive) gain, the technique used
520  in Speex is similar to G.728 (LD-CELP).
521  However since we do not have a low-delay constraint, the search can be
522  made more 
523 \begin_inset Quotes eld
524 \end_inset 
525
526 global
527 \begin_inset Quotes erd
528 \end_inset 
529
530  and make use of the whole information available for a sub-frame.
531 \layout Subsection
532
533 Bit allocation
534 \layout Standard
535
536
537 \begin_inset  Tabular
538 <lyxtabular version="3" rows="11" columns="9">
539 <features>
540 <column alignment="center" valignment="top" leftline="true" width="0pt">
541 <column alignment="center" valignment="top" leftline="true" width="0pt">
542 <column alignment="center" valignment="top" leftline="true" width="0pt">
543 <column alignment="center" valignment="top" leftline="true" width="0pt">
544 <column alignment="center" valignment="top" leftline="true" width="0pt">
545 <column alignment="center" valignment="top" leftline="true" width="0pt">
546 <column alignment="center" valignment="top" leftline="true" width="0pt">
547 <column alignment="center" valignment="top" leftline="true" width="0pt">
548 <column alignment="center" valignment="top" leftline="true" rightline="true" width="0pt">
549 <row topline="true" bottomline="true">
550 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
551 \begin_inset Text
552
553 \layout Standard
554
555 Parameter
556 \end_inset 
557 </cell>
558 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
559 \begin_inset Text
560
561 \layout Standard
562
563 Update rate
564 \end_inset 
565 </cell>
566 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
567 \begin_inset Text
568
569 \layout Standard
570
571 0
572 \end_inset 
573 </cell>
574 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
575 \begin_inset Text
576
577 \layout Standard
578
579 1
580 \end_inset 
581 </cell>
582 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
583 \begin_inset Text
584
585 \layout Standard
586
587 2
588 \end_inset 
589 </cell>
590 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
591 \begin_inset Text
592
593 \layout Standard
594
595 3
596 \end_inset 
597 </cell>
598 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
599 \begin_inset Text
600
601 \layout Standard
602
603 4
604 \end_inset 
605 </cell>
606 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
607 \begin_inset Text
608
609 \layout Standard
610
611 5
612 \end_inset 
613 </cell>
614 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
615 \begin_inset Text
616
617 \layout Standard
618
619 6
620 \end_inset 
621 </cell>
622 </row>
623 <row topline="true">
624 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
625 \begin_inset Text
626
627 \layout Standard
628
629 LSP
630 \end_inset 
631 </cell>
632 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
633 \begin_inset Text
634
635 \layout Standard
636
637 frame
638 \end_inset 
639 </cell>
640 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
641 \begin_inset Text
642
643 \layout Standard
644
645 4
646 \end_inset 
647 </cell>
648 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
649 \begin_inset Text
650
651 \layout Standard
652
653 4
654 \end_inset 
655 </cell>
656 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
657 \begin_inset Text
658
659 \layout Standard
660
661 4
662 \end_inset 
663 </cell>
664 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
665 \begin_inset Text
666
667 \layout Standard
668
669 4
670 \end_inset 
671 </cell>
672 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
673 \begin_inset Text
674
675 \layout Standard
676
677 4
678 \end_inset 
679 </cell>
680 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
681 \begin_inset Text
682
683 \layout Standard
684
685 4
686 \end_inset 
687 </cell>
688 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
689 \begin_inset Text
690
691 \layout Standard
692
693 4
694 \end_inset 
695 </cell>
696 </row>
697 <row topline="true">
698 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
699 \begin_inset Text
700
701 \layout Standard
702
703 LSP
704 \end_inset 
705 </cell>
706 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
707 \begin_inset Text
708
709 \layout Standard
710
711 frame
712 \end_inset 
713 </cell>
714 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
715 \begin_inset Text
716
717 \layout Standard
718
719 0
720 \end_inset 
721 </cell>
722 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
723 \begin_inset Text
724
725 \layout Standard
726
727 18
728 \end_inset 
729 </cell>
730 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
731 \begin_inset Text
732
733 \layout Standard
734
735 18
736 \end_inset 
737 </cell>
738 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
739 \begin_inset Text
740
741 \layout Standard
742
743 18
744 \end_inset 
745 </cell>
746 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
747 \begin_inset Text
748
749 \layout Standard
750
751 18
752 \end_inset 
753 </cell>
754 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
755 \begin_inset Text
756
757 \layout Standard
758
759 30
760 \end_inset 
761 </cell>
762 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
763 \begin_inset Text
764
765 \layout Standard
766
767 30
768 \end_inset 
769 </cell>
770 </row>
771 <row topline="true">
772 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
773 \begin_inset Text
774
775 \layout Standard
776
777 OL pitch
778 \end_inset 
779 </cell>
780 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
781 \begin_inset Text
782
783 \layout Standard
784
785 frame
786 \end_inset 
787 </cell>
788 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
789 \begin_inset Text
790
791 \layout Standard
792
793 0
794 \end_inset 
795 </cell>
796 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
797 \begin_inset Text
798
799 \layout Standard
800
801 7
802 \end_inset 
803 </cell>
804 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
805 \begin_inset Text
806
807 \layout Standard
808
809 7
810 \end_inset 
811 </cell>
812 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
813 \begin_inset Text
814
815 \layout Standard
816
817 0
818 \end_inset 
819 </cell>
820 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
821 \begin_inset Text
822
823 \layout Standard
824
825 0
826 \end_inset 
827 </cell>
828 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
829 \begin_inset Text
830
831 \layout Standard
832
833 0
834 \end_inset 
835 </cell>
836 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
837 \begin_inset Text
838
839 \layout Standard
840
841 0
842 \end_inset 
843 </cell>
844 </row>
845 <row topline="true">
846 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
847 \begin_inset Text
848
849 \layout Standard
850
851 OL pitch gain
852 \end_inset 
853 </cell>
854 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
855 \begin_inset Text
856
857 \layout Standard
858
859 frame
860 \end_inset 
861 </cell>
862 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
863 \begin_inset Text
864
865 \layout Standard
866
867 0
868 \end_inset 
869 </cell>
870 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
871 \begin_inset Text
872
873 \layout Standard
874
875 4
876 \end_inset 
877 </cell>
878 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
879 \begin_inset Text
880
881 \layout Standard
882
883 0
884 \end_inset 
885 </cell>
886 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
887 \begin_inset Text
888
889 \layout Standard
890
891 0
892 \end_inset 
893 </cell>
894 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
895 \begin_inset Text
896
897 \layout Standard
898
899 0
900 \end_inset 
901 </cell>
902 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
903 \begin_inset Text
904
905 \layout Standard
906
907 0
908 \end_inset 
909 </cell>
910 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
911 \begin_inset Text
912
913 \layout Standard
914
915 0
916 \end_inset 
917 </cell>
918 </row>
919 <row topline="true">
920 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
921 \begin_inset Text
922
923 \layout Standard
924
925 Exc gain
926 \end_inset 
927 </cell>
928 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
929 \begin_inset Text
930
931 \layout Standard
932
933 frame
934 \end_inset 
935 </cell>
936 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
937 \begin_inset Text
938
939 \layout Standard
940
941 0
942 \end_inset 
943 </cell>
944 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
945 \begin_inset Text
946
947 \layout Standard
948
949 5
950 \end_inset 
951 </cell>
952 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
953 \begin_inset Text
954
955 \layout Standard
956
957 5
958 \end_inset 
959 </cell>
960 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
961 \begin_inset Text
962
963 \layout Standard
964
965 5
966 \end_inset 
967 </cell>
968 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
969 \begin_inset Text
970
971 \layout Standard
972
973 5
974 \end_inset 
975 </cell>
976 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
977 \begin_inset Text
978
979 \layout Standard
980
981 5
982 \end_inset 
983 </cell>
984 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
985 \begin_inset Text
986
987 \layout Standard
988
989 5
990 \end_inset 
991 </cell>
992 </row>
993 <row topline="true">
994 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
995 \begin_inset Text
996
997 \layout Standard
998
999 Fine pitch
1000 \end_inset 
1001 </cell>
1002 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1003 \begin_inset Text
1004
1005 \layout Standard
1006
1007 subframe
1008 \end_inset 
1009 </cell>
1010 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1011 \begin_inset Text
1012
1013 \layout Standard
1014
1015 0
1016 \end_inset 
1017 </cell>
1018 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1019 \begin_inset Text
1020
1021 \layout Standard
1022
1023 0
1024 \end_inset 
1025 </cell>
1026 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1027 \begin_inset Text
1028
1029 \layout Standard
1030
1031 0
1032 \end_inset 
1033 </cell>
1034 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1035 \begin_inset Text
1036
1037 \layout Standard
1038
1039 7
1040 \end_inset 
1041 </cell>
1042 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1043 \begin_inset Text
1044
1045 \layout Standard
1046
1047 7
1048 \end_inset 
1049 </cell>
1050 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1051 \begin_inset Text
1052
1053 \layout Standard
1054
1055 7
1056 \end_inset 
1057 </cell>
1058 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1059 \begin_inset Text
1060
1061 \layout Standard
1062
1063 7
1064 \end_inset 
1065 </cell>
1066 </row>
1067 <row topline="true">
1068 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1069 \begin_inset Text
1070
1071 \layout Standard
1072
1073 Pitch gain
1074 \end_inset 
1075 </cell>
1076 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1077 \begin_inset Text
1078
1079 \layout Standard
1080
1081 subframe
1082 \end_inset 
1083 </cell>
1084 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1085 \begin_inset Text
1086
1087 \layout Standard
1088
1089 0
1090 \end_inset 
1091 </cell>
1092 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1093 \begin_inset Text
1094
1095 \layout Standard
1096
1097 0
1098 \end_inset 
1099 </cell>
1100 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1101 \begin_inset Text
1102
1103 \layout Standard
1104
1105 5
1106 \end_inset 
1107 </cell>
1108 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1109 \begin_inset Text
1110
1111 \layout Standard
1112
1113 5
1114 \end_inset 
1115 </cell>
1116 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1117 \begin_inset Text
1118
1119 \layout Standard
1120
1121 5
1122 \end_inset 
1123 </cell>
1124 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1125 \begin_inset Text
1126
1127 \layout Standard
1128
1129 7
1130 \end_inset 
1131 </cell>
1132 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1133 \begin_inset Text
1134
1135 \layout Standard
1136
1137 7
1138 \end_inset 
1139 </cell>
1140 </row>
1141 <row topline="true">
1142 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1143 \begin_inset Text
1144
1145 \layout Standard
1146
1147 Innovation gain
1148 \end_inset 
1149 </cell>
1150 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1151 \begin_inset Text
1152
1153 \layout Standard
1154
1155 subframe
1156 \end_inset 
1157 </cell>
1158 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1159 \begin_inset Text
1160
1161 \layout Standard
1162
1163 0
1164 \end_inset 
1165 </cell>
1166 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1167 \begin_inset Text
1168
1169 \layout Standard
1170
1171 3
1172 \end_inset 
1173 </cell>
1174 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1175 \begin_inset Text
1176
1177 \layout Standard
1178
1179 0
1180 \end_inset 
1181 </cell>
1182 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1183 \begin_inset Text
1184
1185 \layout Standard
1186
1187 3
1188 \end_inset 
1189 </cell>
1190 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1191 \begin_inset Text
1192
1193 \layout Standard
1194
1195 3
1196 \end_inset 
1197 </cell>
1198 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1199 \begin_inset Text
1200
1201 \layout Standard
1202
1203 3
1204 \end_inset 
1205 </cell>
1206 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1207 \begin_inset Text
1208
1209 \layout Standard
1210
1211 3
1212 \end_inset 
1213 </cell>
1214 </row>
1215 <row topline="true" bottomline="true">
1216 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1217 \begin_inset Text
1218
1219 \layout Standard
1220
1221 Innovation VQ
1222 \end_inset 
1223 </cell>
1224 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1225 \begin_inset Text
1226
1227 \layout Standard
1228
1229 subframe
1230 \end_inset 
1231 </cell>
1232 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1233 \begin_inset Text
1234
1235 \layout Standard
1236
1237 0
1238 \end_inset 
1239 </cell>
1240 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1241 \begin_inset Text
1242
1243 \layout Standard
1244
1245 0
1246 \end_inset 
1247 </cell>
1248 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1249 \begin_inset Text
1250
1251 \layout Standard
1252
1253 16
1254 \end_inset 
1255 </cell>
1256 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1257 \begin_inset Text
1258
1259 \layout Standard
1260
1261 20
1262 \end_inset 
1263 </cell>
1264 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1265 \begin_inset Text
1266
1267 \layout Standard
1268
1269 35
1270 \end_inset 
1271 </cell>
1272 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1273 \begin_inset Text
1274
1275 \layout Standard
1276
1277 48
1278 \end_inset 
1279 </cell>
1280 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1281 \begin_inset Text
1282
1283 \layout Standard
1284
1285 64
1286 \end_inset 
1287 </cell>
1288 </row>
1289 <row topline="true" bottomline="true">
1290 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1291 \begin_inset Text
1292
1293 \layout Standard
1294
1295 Total
1296 \end_inset 
1297 </cell>
1298 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1299 \begin_inset Text
1300
1301 \layout Standard
1302
1303 frame
1304 \end_inset 
1305 </cell>
1306 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1307 \begin_inset Text
1308
1309 \layout Standard
1310
1311 4
1312 \end_inset 
1313 </cell>
1314 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1315 \begin_inset Text
1316
1317 \layout Standard
1318
1319 50
1320 \end_inset 
1321 </cell>
1322 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1323 \begin_inset Text
1324
1325 \layout Standard
1326
1327 118
1328 \end_inset 
1329 </cell>
1330 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1331 \begin_inset Text
1332
1333 \layout Standard
1334
1335 167
1336 \end_inset 
1337 </cell>
1338 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1339 \begin_inset Text
1340
1341 \layout Standard
1342
1343 227
1344 \end_inset 
1345 </cell>
1346 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
1347 \begin_inset Text
1348
1349 \layout Standard
1350
1351 299
1352 \end_inset 
1353 </cell>
1354 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
1355 \begin_inset Text
1356
1357 \layout Standard
1358
1359 363
1360 \end_inset 
1361 </cell>
1362 </row>
1363 </lyxtabular>
1364
1365 \end_inset 
1366
1367
1368 \layout Subsection
1369
1370 Perceptual post-filter
1371 \layout Standard
1372
1373 This part of the codec only applies to the decoder and can even be changed
1374  without affecting inter-operability.
1375  
1376 \layout Section
1377
1378 Speex wideband mode (sub-band CELP)
1379 \layout Standard
1380
1381 For wideband, the Speex approach is similar to the ITU-T G.722 (ADPCM) wideband
1382  standard in that it uses a 
1383 \emph on 
1384 q
1385 \emph default 
1386 uadrature 
1387 \emph on 
1388 m
1389 \emph default 
1390 irror 
1391 \emph on 
1392 f
1393 \emph default 
1394 ilter (QMF) to split the band in two.
1395  The 16 kHz signal is thus divided into two 8 kHz signals, one representing
1396  the low band (0-4 kHz), the other the high band (4-8 kHz).
1397  The low band is encoded with the narrowband mode described in section 
1398 \begin_inset LatexCommand \ref{sec:Speex-narrowband-mode}
1399
1400 \end_inset 
1401
1402  in such a way that the resulting 
1403 \begin_inset Quotes eld
1404 \end_inset 
1405
1406 embedded narrowband bit-stream
1407 \begin_inset Quotes erd
1408 \end_inset 
1409
1410  can also be decoded with the narrowband decoder.
1411  Since the low band encoding has already been described only the high band
1412  encoding is described in this section.
1413 \layout Subsection
1414
1415 Linear Prediction
1416 \layout Standard
1417
1418 The linear prediction part used for the high-band is very similar to what
1419  is done for narrowband.
1420  The only difference is that we use only 12 bits to encode the high-band
1421  LSP's.
1422 \layout Subsection
1423
1424 Pitch Prediction
1425 \layout Standard
1426
1427 That part is easy: there's no pitch prediction for the high-band.
1428  There are two reasons for that.
1429  First, there is usually little harmonic structure in this band (above 4
1430  kHz).
1431  Second, it would be very hard to implement since the QMF folds the 4-8
1432  kHz band into 4-0 kHz (reversing the frequency axis), which means that
1433  the location of the harmonics are no longer at multiples of the fundamental
1434  (pitch).
1435 \layout Subsection
1436
1437 Excitation Quantization
1438 \layout Standard
1439
1440 The high-band excitation is coded in the same way as for narrowband.
1441  
1442 \layout Section
1443
1444 Programming with Speex (the libspeex API)
1445 \layout Subsection
1446
1447 Encoding
1448 \layout Standard
1449
1450 In order to encode speech using Speex, you first need to:
1451 \layout LyX-Code
1452
1453 #include <speex.h>
1454 \layout Standard
1455
1456 You then need to declare a Speex bit-packing struct
1457 \layout LyX-Code
1458
1459 SpeexBits bits;
1460 \layout Standard
1461
1462 and a Speex encoder state
1463 \layout LyX-Code
1464
1465 void *enc_state;
1466 \layout Standard
1467
1468 The two are initialized by:
1469 \layout LyX-Code
1470
1471 speex_bits_init(&bits);
1472 \layout LyX-Code
1473
1474 enc_state = speex_encoder_init(&speex_nb_mode);
1475 \layout Standard
1476
1477 For wideband coding, 
1478 \emph on 
1479 speex_nb_mode
1480 \emph default 
1481  will be replaced by 
1482 \emph on 
1483 speex_wb_mode
1484 \emph default 
1485 .
1486  In most cases, you will need to know the frame size used by the mode you
1487  are using.
1488  You can get that value in the 
1489 \emph on 
1490 frame_size
1491 \emph default 
1492  variable with:
1493 \layout LyX-Code
1494
1495 speex_encoder_ctl(enc_state,SPEEX_GET_FRAME_SIZE,&frame_size);
1496 \layout Standard
1497
1498 Once the initialization is done, for every input frame:
1499 \layout LyX-Code
1500
1501 speex_bits_reset(&bits);
1502 \layout LyX-Code
1503
1504 speex_encode(enc_state, input_frame, &bits);
1505 \layout LyX-Code
1506
1507 nbBytes = speex_bits_write(&bits, byte_ptr, MAX_NB_BYTES);
1508 \layout Standard
1509
1510 where 
1511 \emph on 
1512 input_frame
1513 \emph default 
1514  is a 
1515 \emph on 
1516 (float *)
1517 \emph default 
1518  pointing to the beginning of a speech frame, 
1519 \emph on 
1520 byte_ptr
1521 \emph default 
1522  is a 
1523 \emph on 
1524 (char *)
1525 \emph default 
1526  where the encoded frame will be written, 
1527 \emph on 
1528 MAX_NB_BYTES
1529 \emph default 
1530  is the maximum number of bytes that can be written to 
1531 \emph on 
1532 byte_ptr
1533 \emph default 
1534  without causing an overflow and 
1535 \emph on 
1536 nbBytes
1537 \emph default 
1538  is the number of bytes actually written to 
1539 \emph on 
1540 byte_ptr
1541 \emph default 
1542  (the encoded size in bytes).
1543  Before calling speex_bits_write, it is possible to find the number of bytes
1544  that need to be written by calling 
1545 \family typewriter 
1546 speex_bits_nbytes(&bits)
1547 \family default 
1548 , which returns a number of bytes.
1549  
1550 \layout Standard
1551
1552 After you're done with the encoding, free all resources with:
1553 \layout LyX-Code
1554
1555 speex_bits_destroy(&bits);
1556 \layout LyX-Code
1557
1558 speex_encoder_destroy(&enc_state);
1559 \layout Standard
1560
1561 That's about it for the encoder.
1562  
1563 \layout Subsection
1564
1565 Decoding
1566 \layout Standard
1567
1568 In order to encode speech using Speex, you first need to:
1569 \layout LyX-Code
1570
1571 #include <speex.h>
1572 \layout Standard
1573
1574 You then need to declare a Speex bit-packing struct
1575 \layout LyX-Code
1576
1577 SpeexBits bits;
1578 \layout Standard
1579
1580 and a Speex encoder state
1581 \layout LyX-Code
1582
1583 void *dec_state;
1584 \layout Standard
1585
1586 The two are initialized by:
1587 \layout LyX-Code
1588
1589 speex_bits_init(&bits);
1590 \layout LyX-Code
1591
1592 dec_state = speex_decoder_init(&speex_nb_mode);
1593 \layout Standard
1594
1595 For wideband decoding, 
1596 \emph on 
1597 speex_nb_mode
1598 \emph default 
1599  will be replaced by 
1600 \emph on 
1601 speex_wb_mode
1602 \emph default 
1603 .
1604  You can get that value in the 
1605 \emph on 
1606 frame_size
1607 \emph default 
1608  variable with:
1609 \layout LyX-Code
1610
1611 speex_decoder_ctl(dec_state, SPEEX_GET_FRAME_SIZE, &frame_size); 
1612 \layout Standard
1613
1614 There is also a parameter that can be set for the decoder: whether or not
1615  to use a perceptual post-filter.
1616  This can be set by: 
1617 \layout LyX-Code
1618
1619 speex_decoder_ctl(dec_state, SPEEX_SET_PF, &pf); 
1620 \layout Standard
1621
1622 where pf is an int that with value 0 to have the post-filter disabled and
1623  1 to have it enabled.
1624 \layout Standard
1625
1626 Again, once the decoder initialization is done, for every input frame:
1627 \layout LyX-Code
1628
1629 speex_bits_read_from(&bits, input_bytes, nbBytes);
1630 \layout LyX-Code
1631
1632 speex_decode(st, &bits, output_frame, 0);
1633 \layout Standard
1634
1635 where input_bytes is a 
1636 \emph on 
1637 (char *)
1638 \emph default 
1639  containing the bit-stream data received for a frame, 
1640 \emph on 
1641 nbBytes
1642 \emph default 
1643  is the size (in bytes) of that bit-stream, and 
1644 \emph on 
1645 output_frame
1646 \emph default 
1647  is a 
1648 \emph on 
1649 (float *)
1650 \emph default 
1651  and points to the area where the decoded speech frame will be written.
1652  The last argument indicates whether the frame we'd like to decode was lost.
1653  A value of 0 indicates the normal case where bits points to the bit of
1654  the current frame.
1655  A value of 1 indicates that we don't have the bits for the current frame,
1656  in which case the bits argument should be the same as the bits for the
1657  last correctly received frame.
1658  When a frame is lost, the Speex decoder will do its best to "guess" the
1659  correct signal.
1660 \layout Subsection
1661
1662 Codec Options (speex_*_ctl)
1663 \layout Standard
1664
1665 The Speex encoder and decoder support many options and requests that can
1666  be accessed through the 
1667 \emph on 
1668 speex_encoder_ctl
1669 \emph default 
1670  and 
1671 \emph on 
1672 speex_decoder_ctl
1673 \emph default 
1674  functions.
1675  These functions are similar the the 
1676 \emph on 
1677 ioctl
1678 \emph default 
1679  system call and their prototypes are:
1680 \layout LyX-Code
1681
1682 void speex_encoder_ctl(void *encoder, int request, void *ptr);
1683 \layout LyX-Code
1684
1685 void speex_decoder_ctl(void *encoder, int request, void *ptr);
1686 \layout Standard
1687
1688 The different values of request allowed are (note that some only apply to
1689  the encoder or the decoder):
1690 \layout Description
1691
1692 SPEEX_SET_PF** Set post-filter to on (1) or off (0) (integer)
1693 \layout Description
1694
1695 SPEEX_GET_PF** Get post-filter status (integer)
1696 \layout Description
1697
1698 SPEEX_GET_FRAME_SIZE Get the frame size used for the current mode (integer)
1699 \layout Description
1700
1701 SPEEX_SET_QUALITY* Set the encoder speech quality (integer 0 to 10)
1702 \layout Description
1703
1704 SPEEX_GET_QUALITY* Get the current encoder speech quality (integer 0 to
1705  10)
1706 \layout Description
1707
1708 SPEEX_SET_MODE*
1709 \begin_inset Formula $\dagger $
1710 \end_inset 
1711
1712
1713 \layout Description
1714
1715 SPEEX_GET_MODE*
1716 \begin_inset Formula $\dagger $
1717 \end_inset 
1718
1719
1720 \layout Description
1721
1722 SPEEX_SET_LOW_MODE*
1723 \begin_inset Formula $\dagger $
1724 \end_inset 
1725
1726
1727 \layout Description
1728
1729 SPEEX_GET_LOW_MODE*
1730 \begin_inset Formula $\dagger $
1731 \end_inset 
1732
1733
1734 \layout Description
1735
1736 SPEEX_SET_HIGH_MODE*
1737 \begin_inset Formula $\dagger $
1738 \end_inset 
1739
1740
1741 \layout Description
1742
1743 SPEEX_GET_HIGH_MODE*
1744 \begin_inset Formula $\dagger $
1745 \end_inset 
1746
1747
1748 \layout Description
1749
1750 SPEEX_SET_VBR* Set variable bit-rate (VBR) to on (1) or off (0) (integer)
1751 \layout Description
1752
1753 SPEEX_GET_VBR* Get variable bit-rate (VBR) status (integer)
1754 \layout Description
1755
1756 SPEEX_SET_VBR_QUALITY* Set the encoder VBR speech quality (integer 0 to
1757  10)
1758 \layout Description
1759
1760 SPEEX_GET_VBR_QUALITY* Get the current encoder VBR speech quality (integer
1761  0 to 10)
1762 \layout Description
1763
1764 * applies only to the encoder
1765 \layout Description
1766
1767 ** applies only to the decoder
1768 \layout Description
1769
1770
1771 \begin_inset Formula $\dagger $
1772 \end_inset 
1773
1774  normally only used internally
1775 \layout Section
1776
1777 Formats and standards
1778 \layout Standard
1779
1780 Speex can encode speech in both narrowband and wideband and provides different
1781  bit-rates.
1782  All modes of operation MUST be supported at the decoder and at least one
1783  MUST be supported by the encoder.
1784  The main reason is that not all platforms may be able to handle the complexity
1785  of encoding for all modes.
1786 \layout Subsection
1787
1788 RTP Payload Format
1789 \layout Standard
1790
1791 Since Speex encoded frames already contain mode information, they can be
1792  sent without any other information in an RTP packet.
1793  If more than one frame is transmitted, no byte padding is performed at
1794  the end of frames, except the last one.
1795 \layout Subsection
1796
1797 Ogg file format
1798 \layout Standard
1799
1800 Speex bit-streams can be stored in Ogg files.
1801  In this case, the first packet of the Ogg file contains the Speex header
1802  (see speex_header.h for now) and the second packet contains comments.
1803  The next frames contain one or more (number found in header) Speex frames.
1804  (Note: packing more that one Speex frame in an Ogg frame is not supported
1805  yet)
1806 \layout LyX-Code
1807
1808 \layout Section
1809 \pagebreak_top \start_of_appendix 
1810 GNU Free Documentation License
1811 \layout Standard
1812
1813 Version 1.1, March 2000
1814 \layout Standard
1815
1816 Copyright (C) 2000 Free Software Foundation, Inc.
1817  59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted
1818  to copy and distribute verbatim copies of this license document, but changing
1819  it is not allowed.
1820  
1821 \layout Subsection*
1822
1823 0.
1824  PREAMBLE
1825 \layout Standard
1826
1827 The purpose of this License is to make a manual, textbook, or other written
1828  document "free" in the sense of freedom: to assure everyone the effective
1829  freedom to copy and redistribute it, with or without modifying it, either
1830  commercially or noncommercially.
1831  Secondarily, this License preserves for the author and publisher a way
1832  to get credit for their work, while not being considered responsible for
1833  modifications made by others.
1834 \layout Standard
1835
1836 This License is a kind of "copyleft", which means that derivative works
1837  of the document must themselves be free in the same sense.
1838  It complements the GNU General Public License, which is a copyleft license
1839  designed for free software.
1840 \layout Standard
1841
1842 We have designed this License in order to use it for manuals for free software,
1843  because free software needs free documentation: a free program should come
1844  with manuals providing the same freedoms that the software does.
1845  But this License is not limited to software manuals; it can be used for
1846  any textual work, regardless of subject matter or whether it is published
1847  as a printed book.
1848  We recommend this License principally for works whose purpose is instruction
1849  or reference.
1850  
1851 \layout Subsection*
1852
1853 1.
1854  APPLICABILITY AND DEFINITIONS
1855 \layout Standard
1856
1857 This License applies to any manual or other work that contains a notice
1858  placed by the copyright holder saying it can be distributed under the terms
1859  of this License.
1860  The "Document", below, refers to any such manual or work.
1861  Any member of the public is a licensee, and is addressed as "you".
1862 \layout Standard
1863
1864 A "Modified Version" of the Document means any work containing the Document
1865  or a portion of it, either copied verbatim, or with modifications and/or
1866  translated into another language.
1867 \layout Standard
1868
1869 A "Secondary Section" is a named appendix or a front-matter section of the
1870  Document that deals exclusively with the relationship of the publishers
1871  or authors of the Document to the Document's overall subject (or to related
1872  matters) and contains nothing that could fall directly within that overall
1873  subject.
1874  (For example, if the Document is in part a textbook of mathematics, a Secondary
1875  Section may not explain any mathematics.) The relationship could be a matter
1876  of historical connection with the subject or with related matters, or of
1877  legal, commercial, philosophical, ethical or political position regarding
1878  them.
1879 \layout Standard
1880
1881 The "Invariant Sections" are certain Secondary Sections whose titles are
1882  designated, as being those of Invariant Sections, in the notice that says
1883  that the Document is released under this License.
1884 \layout Standard
1885
1886 The "Cover Texts" are certain short passages of text that are listed, as
1887  Front-Cover Texts or Back-Cover Texts, in the notice that says that the
1888  Document is released under this License.
1889 \layout Standard
1890
1891 A "Transparent" copy of the Document means a machine-readable copy, represented
1892  in a format whose specification is available to the general public, whose
1893  contents can be viewed and edited directly and straightforwardly with generic
1894  text editors or (for images composed of pixels) generic paint programs
1895  or (for drawings) some widely available drawing editor, and that is suitable
1896  for input to text formatters or for automatic translation to a variety
1897  of formats suitable for input to text formatters.
1898  A copy made in an otherwise Transparent file format whose markup has been
1899  designed to thwart or discourage subsequent modification by readers is
1900  not Transparent.
1901  A copy that is not "Transparent" is called "Opaque".
1902 \layout Standard
1903
1904 Examples of suitable formats for Transparent copies include plain ASCII
1905  without markup, Texinfo input format, LaTeX input format, SGML or XML using
1906  a publicly available DTD, and standard-conforming simple HTML designed
1907  for human modification.
1908  Opaque formats include PostScript, PDF, proprietary formats that can be
1909  read and edited only by proprietary word processors, SGML or XML for which
1910  the DTD and/or processing tools are not generally available, and the machine-ge
1911 nerated HTML produced by some word processors for output purposes only.
1912 \layout Standard
1913
1914 The "Title Page" means, for a printed book, the title page itself, plus
1915  such following pages as are needed to hold, legibly, the material this
1916  License requires to appear in the title page.
1917  For works in formats which do not have any title page as such, "Title Page"
1918  means the text near the most prominent appearance of the work's title,
1919  preceding the beginning of the body of the text.
1920 \layout Subsection*
1921
1922 2.
1923  VERBATIM COPYING
1924 \layout Standard
1925
1926 You may copy and distribute the Document in any medium, either commercially
1927  or noncommercially, provided that this License, the copyright notices,
1928  and the license notice saying this License applies to the Document are
1929  reproduced in all copies, and that you add no other conditions whatsoever
1930  to those of this License.
1931  You may not use technical measures to obstruct or control the reading or
1932  further copying of the copies you make or distribute.
1933  However, you may accept compensation in exchange for copies.
1934  If you distribute a large enough number of copies you must also follow
1935  the conditions in section 3.
1936 \layout Standard
1937
1938 You may also lend copies, under the same conditions stated above, and you
1939  may publicly display copies.
1940 \layout Subsection*
1941
1942 3.
1943  COPYING IN QUANTITY
1944 \layout Standard
1945
1946 If you publish printed copies of the Document numbering more than 100, and
1947  the Document's license notice requires Cover Texts, you must enclose the
1948  copies in covers that carry, clearly and legibly, all these Cover Texts:
1949  Front-Cover Texts on the front cover, and Back-Cover Texts on the back
1950  cover.
1951  Both covers must also clearly and legibly identify you as the publisher
1952  of these copies.
1953  The front cover must present the full title with all words of the title
1954  equally prominent and visible.
1955  You may add other material on the covers in addition.
1956  Copying with changes limited to the covers, as long as they preserve the
1957  title of the Document and satisfy these conditions, can be treated as verbatim
1958  copying in other respects.
1959 \layout Standard
1960
1961 If the required texts for either cover are too voluminous to fit legibly,
1962  you should put the first ones listed (as many as fit reasonably) on the
1963  actual cover, and continue the rest onto adjacent pages.
1964 \layout Standard
1965
1966 If you publish or distribute Opaque copies of the Document numbering more
1967  than 100, you must either include a machine-readable Transparent copy along
1968  with each Opaque copy, or state in or with each Opaque copy a publicly-accessib
1969 le computer-network location containing a complete Transparent copy of the
1970  Document, free of added material, which the general network-using public
1971  has access to download anonymously at no charge using public-standard network
1972  protocols.
1973  If you use the latter option, you must take reasonably prudent steps, when
1974  you begin distribution of Opaque copies in quantity, to ensure that this
1975  Transparent copy will remain thus accessible at the stated location until
1976  at least one year after the last time you distribute an Opaque copy (directly
1977  or through your agents or retailers) of that edition to the public.
1978 \layout Standard
1979
1980 It is requested, but not required, that you contact the authors of the Document
1981  well before redistributing any large number of copies, to give them a chance
1982  to provide you with an updated version of the Document.
1983  
1984 \layout Subsection*
1985
1986 4.
1987  MODIFICATIONS
1988 \layout Standard
1989
1990 You may copy and distribute a Modified Version of the Document under the
1991  conditions of sections 2 and 3 above, provided that you release the Modified
1992  Version under precisely this License, with the Modified Version filling
1993  the role of the Document, thus licensing distribution and modification
1994  of the Modified Version to whoever possesses a copy of it.
1995  In addition, you must do these things in the Modified Version: 
1996 \layout Itemize
1997
1998 A.
1999  Use in the Title Page (and on the covers, if any) a title distinct from
2000  that of the Document, and from those of previous versions (which should,
2001  if there were any, be listed in the History section of the Document).
2002  You may use the same title as a previous version if the original publisher
2003  of that version gives permission.
2004 \layout Itemize
2005
2006 B.
2007  List on the Title Page, as authors, one or more persons or entities responsible
2008  for authorship of the modifications in the Modified Version, together with
2009  at least five of the principal authors of the Document (all of its principal
2010  authors, if it has less than five).
2011 \layout Itemize
2012
2013 C.
2014  State on the Title page the name of the publisher of the Modified Version,
2015  as the publisher.
2016 \layout Itemize
2017
2018 D.
2019  Preserve all the copyright notices of the Document.
2020 \layout Itemize
2021
2022 E.
2023  Add an appropriate copyright notice for your modifications adjacent to
2024  the other copyright notices.
2025 \layout Itemize
2026
2027 F.
2028  Include, immediately after the copyright notices, a license notice giving
2029  the public permission to use the Modified Version under the terms of this
2030  License, in the form shown in the Addendum below.
2031 \layout Itemize
2032
2033 G.
2034  Preserve in that license notice the full lists of Invariant Sections and
2035  required Cover Texts given in the Document's license notice.
2036 \layout Itemize
2037
2038 H.
2039  Include an unaltered copy of this License.
2040 \layout Itemize
2041
2042 I.
2043  Preserve the section entitled "History", and its title, and add to it an
2044  item stating at least the title, year, new authors, and publisher of the
2045  Modified Version as given on the Title Page.
2046  If there is no section entitled "History" in the Document, create one stating
2047  the title, year, authors, and publisher of the Document as given on its
2048  Title Page, then add an item describing the Modified Version as stated
2049  in the previous sentence.
2050 \layout Itemize
2051
2052 J.
2053  Preserve the network location, if any, given in the Document for public
2054  access to a Transparent copy of the Document, and likewise the network
2055  locations given in the Document for previous versions it was based on.
2056  These may be placed in the "History" section.
2057  You may omit a network location for a work that was published at least
2058  four years before the Document itself, or if the original publisher of
2059  the version it refers to gives permission.
2060 \layout Itemize
2061
2062 K.
2063  In any section entitled "Acknowledgements" or "Dedications", preserve the
2064  section's title, and preserve in the section all the substance and tone
2065  of each of the contributor acknowledgements and/or dedications given therein.
2066 \layout Itemize
2067
2068 L.
2069  Preserve all the Invariant Sections of the Document, unaltered in their
2070  text and in their titles.
2071  Section numbers or the equivalent are not considered part of the section
2072  titles.
2073 \layout Itemize
2074
2075 M.
2076  Delete any section entitled "Endorsements".
2077  Such a section may not be included in the Modified Version.
2078 \layout Itemize
2079
2080 N.
2081  Do not retitle any existing section as "Endorsements" or to conflict in
2082  title with any Invariant Section.
2083  
2084 \layout Standard
2085
2086 If the Modified Version includes new front-matter sections or appendices
2087  that qualify as Secondary Sections and contain no material copied from
2088  the Document, you may at your option designate some or all of these sections
2089  as invariant.
2090  To do this, add their titles to the list of Invariant Sections in the Modified
2091  Version's license notice.
2092  These titles must be distinct from any other section titles.
2093 \layout Standard
2094
2095 You may add a section entitled "Endorsements", provided it contains nothing
2096  but endorsements of your Modified Version by various parties--for example,
2097  statements of peer review or that the text has been approved by an organization
2098  as the authoritative definition of a standard.
2099 \layout Standard
2100
2101 You may add a passage of up to five words as a Front-Cover Text, and a passage
2102  of up to 25 words as a Back-Cover Text, to the end of the list of Cover
2103  Texts in the Modified Version.
2104  Only one passage of Front-Cover Text and one of Back-Cover Text may be
2105  added by (or through arrangements made by) any one entity.
2106  If the Document already includes a cover text for the same cover, previously
2107  added by you or by arrangement made by the same entity you are acting on
2108  behalf of, you may not add another; but you may replace the old one, on
2109  explicit permission from the previous publisher that added the old one.
2110 \layout Standard
2111
2112 The author(s) and publisher(s) of the Document do not by this License give
2113  permission to use their names for publicity for or to assert or imply endorseme
2114 nt of any Modified Version.
2115  
2116 \layout Subsection*
2117
2118 5.
2119  COMBINING DOCUMENTS
2120 \layout Standard
2121
2122 You may combine the Document with other documents released under this License,
2123  under the terms defined in section 4 above for modified versions, provided
2124  that you include in the combination all of the Invariant Sections of all
2125  of the original documents, unmodified, and list them all as Invariant Sections
2126  of your combined work in its license notice.
2127 \layout Standard
2128
2129 The combined work need only contain one copy of this License, and multiple
2130  identical Invariant Sections may be replaced with a single copy.
2131  If there are multiple Invariant Sections with the same name but different
2132  contents, make the title of each such section unique by adding at the end
2133  of it, in parentheses, the name of the original author or publisher of
2134  that section if known, or else a unique number.
2135  Make the same adjustment to the section titles in the list of Invariant
2136  Sections in the license notice of the combined work.
2137 \layout Standard
2138
2139 In the combination, you must combine any sections entitled "History" in
2140  the various original documents, forming one section entitled "History";
2141  likewise combine any sections entitled "Acknowledgements", and any sections
2142  entitled "Dedications".
2143  You must delete all sections entitled "Endorsements."
2144 \layout Subsection*
2145
2146 6.
2147  COLLECTIONS OF DOCUMENTS
2148 \layout Standard
2149
2150 You may make a collection consisting of the Document and other documents
2151  released under this License, and replace the individual copies of this
2152  License in the various documents with a single copy that is included in
2153  the collection, provided that you follow the rules of this License for
2154  verbatim copying of each of the documents in all other respects.
2155 \layout Standard
2156
2157 You may extract a single document from such a collection, and distribute
2158  it individually under this License, provided you insert a copy of this
2159  License into the extracted document, and follow this License in all other
2160  respects regarding verbatim copying of that document.
2161  
2162 \layout Subsection*
2163
2164 7.
2165  AGGREGATION WITH INDEPENDENT WORKS
2166 \layout Standard
2167
2168 A compilation of the Document or its derivatives with other separate and
2169  independent documents or works, in or on a volume of a storage or distribution
2170  medium, does not as a whole count as a Modified Version of the Document,
2171  provided no compilation copyright is claimed for the compilation.
2172  Such a compilation is called an "aggregate", and this License does not
2173  apply to the other self-contained works thus compiled with the Document,
2174  on account of their being thus compiled, if they are not themselves derivative
2175  works of the Document.
2176 \layout Standard
2177
2178 If the Cover Text requirement of section 3 is applicable to these copies
2179  of the Document, then if the Document is less than one quarter of the entire
2180  aggregate, the Document's Cover Texts may be placed on covers that surround
2181  only the Document within the aggregate.
2182  Otherwise they must appear on covers around the whole aggregate.
2183 \layout Subsection*
2184
2185 8.
2186  TRANSLATION
2187 \layout Standard
2188
2189 Translation is considered a kind of modification, so you may distribute
2190  translations of the Document under the terms of section 4.
2191  Replacing Invariant Sections with translations requires special permission
2192  from their copyright holders, but you may include translations of some
2193  or all Invariant Sections in addition to the original versions of these
2194  Invariant Sections.
2195  You may include a translation of this License provided that you also include
2196  the original English version of this License.
2197  In case of a disagreement between the translation and the original English
2198  version of this License, the original English version will prevail.
2199 \layout Subsection*
2200
2201 9.
2202  TERMINATION
2203 \layout Standard
2204
2205 You may not copy, modify, sublicense, or distribute the Document except
2206  as expressly provided for under this License.
2207  Any other attempt to copy, modify, sublicense or distribute the Document
2208  is void, and will automatically terminate your rights under this License.
2209  However, parties who have received copies, or rights, from you under this
2210  License will not have their licenses terminated so long as such parties
2211  remain in full compliance.
2212  
2213 \layout Subsection*
2214
2215 10.
2216  FUTURE REVISIONS OF THIS LICENSE
2217 \layout Standard
2218
2219 The Free Software Foundation may publish new, revised versions of the GNU
2220  Free Documentation License from time to time.
2221  Such new versions will be similar in spirit to the present version, but
2222  may differ in detail to address new problems or concerns.
2223  See http://www.gnu.org/copyleft/.
2224 \layout Standard
2225
2226 Each version of the License is given a distinguishing version number.
2227  If the Document specifies that a particular numbered version of this License
2228  "or any later version" applies to it, you have the option of following
2229  the terms and conditions either of that specified version or of any later
2230  version that has been published (not as a draft) by the Free Software Foundatio
2231 n.
2232  If the Document does not specify a version number of this License, you
2233  may choose any version ever published (not as a draft) by the Free Software
2234  Foundation.
2235 \the_end