# Multimode Tree-Coding of Speech with Pre-/Post-Weighting +
## 6 Tree-Coding  
Tree-coding is a type of analysis-by-synthesis coding structure similar to Code-Excited Linear Prediction (CELP), but differs from CELP in that the codebook has a tree structure and the delay in the analysis-by-synthesis procedure is less [29]. Tree-coding is a natural way to incorporate the analysis-by-synthesis approach into backward adaptive codecs such as G.726/727, leading to expected performance improvements.  
A block diagram of a tree coder for speech is shown in Figure 4. A tree coder consists of a Code Generator, a Code Tree (set of excitations), a Tree Search algorithm, a Distortion calculation, and a Path Map Symbol Release Rule. The Tree Search algorithm, in combination with the code generator and appropriate distortion measure, chooses the best candidate path to the tree depth \(L\) to encode the current input sample. The symbol release rule decides the number of symbols on the best path to transmit or release.  
In tree-coding of speech, the terminology _Code Generator_ refers to the structure that colors the code tree excitations and usually consists of a _short-term predictor_ and a _long-term predictor_.  
The tree code provides the excitation to the code generator to synthesize the reconstructed speech. To construct the tree, we must select the number of branches per node and the number and type of excitation values per branch. Then, the rate of the tree code in bits/sample is obtained from \(R=\frac{1}{\beta}\log\alpha\) where \(\alpha\) is the number of branches/node and \(\beta\) is the number of excitation values/branch. The selection of the number of branches/node and the number and values of the samples/branch are important design choices.  
Once the code tree is designed, we need to search the tree for the best possible path to some depth \(L\). If we have \(\alpha=16\) branches/node (corresponding to a 4-bit quantizer) and \(\beta=1\) excitation value/branch, for a full search, we must search \(16^{L}\) paths to depth \(L\) and there are \(L\) computations per path. Since performance often improves with search depth \(L\), it is obvious that the computational load is immense, particularly since these sequences also must be passed through the recursive code generator. To reduce the computational complexity of searching the full tree to depth \(L\) with minimum cumulative distortion, it is common to use the (\(M\),\(L\)) Tree Search algorithm [30]. This algorithm only retains \(M\) paths at each node. The minimum cumulative distortion path among the \(M\) depth-\(L\) paths is chosen. Then, the path map symbols according to this best path are released or transmitted to the decoder. Different path map symbol release rules are possible. All \(L\) path map symbols can be released and then the tree regenerated according to the (\(M\),\(L\)) algorithm, or some number of symbols less than \(L\) can be released.  
Most users of the (\(M\),\(L\)) algorithm release only the first symbol along the best path, and then extend the \(M\) best paths with that symbol as their root. This is called the _single symbol release rule (SSR)_[31].  
The distortion between the candidate output \(s(k)\) and the input sample \(s(k)\) is computed by filtering the error between them along the depth-\(L\) path through the perceptual error weighting filter similar to that used in CELP, which is of the form  
\[W(z)=\frac{1-\sum_{i=1}^{N}\gamma^{i}a_{i}z^{-i}}{1-\sum_{i=1}^{N}\mu^{i}a_{i}z ^{-i}}, \tag{15}\]  
The distortion values are stored along each searched path map. The path resulting in minimum cumulative distortion is encoded using the symbol release rule. However, the distortion calculation along each path obtained by filtering the error along depth-\(L\) path through the perceptual error weighting filter in Equation (15) is computationally expensive. Therefore, to reduce complexity, perceptual pre-weighting and post-weighting filters can be used, as we do here.