WWW: http://jungfrau.usc.edu/ee577b/fano.html
The fano algorithm is a well known algorithm in communication theory and its efficient implementation is the topic of one of a joint research project between myself, Antonio Ortega, and Keith Chugg. The algorithm is used in communication systems to decode the symbols received over a noisy communication channel. Since this class is in VLSI design, I will first focus on an abstract version of the algorithm and its implementation.
In its most abstract form the fano algorithm is a tree searching algorithm. Consider a tree made up of nodes and branches. Each branch has a weight. Let a path be a sequencees of nodes connected by branches. The weight of path is the sum of the branch metrics. Let paths through from the root to a leaf be called complete paths. The goal of the tree searching algorithm is to try to find the complete path with the lowest weight.
Finding the best complete path is sometimes too expensive and is not strictly required for many applications. The fano algorithm is not guaranteed to find the best complete path, but it usually finds a very good complete path. In communication systems, they perform sophisticated probabilistic analysis to determine how the probability of it finding the best complete path. We are very interested in this algorithm because on average it works well and on average it has much lower compuationally complexity than competitive algorithms.
The fano algorithm searches through the tree sequentially, always moving from one node to a neighboring node until it reaches a leaf node. The fano algorithm uses a concept of a threshold T that it dynamically adjusts to help it decide which way to move during the search. The key steps of the algorithm involve deciding which way to move and when and how to adjust the threshold T. Intuitively speaking, it moves forward only when the partial path to that node has a path weight that satisfies T. If it can't move forward it will try to backtrack and search for other partial paths that satisfy T. If all such partial paths are exhausted, it will loosen the threshold and continue. In addition, when the partial path the algorithm is currently considering looks promissing, it may tighten the threshold. This prevents always backtracking to the root node at the cost of sometimes missing the optimal path.
There are two descriptions of the FANO algorithm I recommend. The first is section 6.4 of the book Principles of Communications Engineering, by J. M. Wozencraft and I. M. Jacobs. and the second is Section 12.2 of the book Error Control Coding: Fundamentals and Applications by S. Lin and D. J. Costello, Jr. Check outside my office for relevant notes.
These textbook descriptions are based on the application of the fano algorithm for communication systems. Consequently, some of the terms that they use may be very unfamiliar to you. Let me see if I can help you out a bit by giving you some introduction to them. Let me first give an introduction to Section 12.2 of Lin and Costello's book.
The data communication area deals with sending information accross a communication media, called a channel. This channel often introduces noise to the infromation that is sent. The principle challenge of communication is to come up with efficient coding and decoding tecniques that enable communication to successfully be transmitted and received despite the noise added to by the channel. One way common way to do that is to encode the data to be sent using a convolutional code . For simplicity we will assume that the data stream that is to be sent across the channel is a stream of bits. This turns out to mean that the term k described in section 12.1 is 1.
In particular, the convolutional code described in section 12.1 uses three bits (m = 3) to encode each data bit sent as described by the G(D) function described at the top of page 351. The first bit is defined as 1 + D. This notation says the first bit is the XOR of the current data and the previous data bit. The second bit is defined as 1 + D^2. This means the second bit to be transmitted is the XOR of the current data bit and the data bit prior to the previous data bit. The third bit is defined to be 1 + D + D^2, referring to the XOR of the current and the last two data bits. Thus for each data bit that you want to send accross the channel, the system sends three instead according to the above encoding. Notice that with this coding each data bit effects the 3-bit information sent accross the channel at the current time and for the next two times. Consequently the information of each data bit is spread over time, giving it the sense of temporal redundancy.
The 1-bit data stream is sent in bursts of size L. For example, in some systems L is 100. In the example described in Section 12.1, L = 5. For our code, after the 5th bit is sent, there are two more zeros sent so that the information of the 5th bit is properly spread over the 5th, 6th, and 7th 3-bit sequences. This is called bring the encoder to the zero state.
The part of the communication system we are interested in is the decoding of the received bits. We get a stream of L+m 3-bit quantities and must guess what was the 1-bit data stream that was sent. If there were no noise, this is very straight forward. By design, the decoder knows which convoluational code was used and it is straight forward to figure out 1-bit data was sent. In fact, this decoding problem can be illustrated using a concept of a code tree, as shown in Figure 12.1. The tree describes the expected output sequence for all possible input sequences of length L=5. The left most branch corresponds to the 0th input bit. The 111 labeling this branch corresponds to the expected output if the first bit is a 1. This is because G(D) = [1 + D, 1 + D^2, 1 + D + D^2] = [1 XOR 0, 1 XOR 0, 1 XOR 0 XOR 0], because D and D^2 are assumed to be 0 initially, which equals [1, 1, 1]. Similarly the lower branch is labelled 000 because G(D) = [0 XOR 0, 0 XOR 0, 0 XOR 0 XOR 0] = 0.
The crux of the problem is that noise in the channel causes the 3-bit quantities to have errors. Thus, the problem of the decoder is to guess which stream of 1-bit data bits were sent based on the noisy 3-bit quantities observered. In principle, the best approach for decoding these L=5 bits would be to consider all possible 1-bit sequences of length 5 and compare the resulting 3-bit sequences of length 7 (each called a code word ) to the observed 3-bit sequence of length 7. The basic idea is to guess the sequence that corresponds to the code word which is closest to observed sequence. The algorithms described in this section describe more efficient ways of finding the "maximum likelihood" sequence that was sent. In fact, the fano algorithm is sub-optimal in that it does not necessarily obtain the closest sequence but usually finds at least a very good one.
The basic way this problem is done is that for every branch the observed 3-bit sequence is compared to the expected 3-bit sequence and a branch metric is obtained which measures how close they are. In Section 12.1 the lower the branch metric, the higher the two are. This metric calculation has a lot of mathematical justification, but the result is shown in Figure 12.2. For every bit that is correct we add one to the branch metric. For every bit that is wrong we subtract 5. Thus if all 3-bits are correct the branch metric is 3. If one is wrong, the branch metric is -3. If two are wrong, the branch metric is -9. If three are wrong, the branch metric is -15. A path metric is simply the sum of the branch metrics along that path.
Section 12.1 goes into two algorithms to find a good path (one with a high branch metric) through the tree, the stack algorithm and the fano algorithm. You should probably read both, but I plan to have you implement only the fano algorithm. You need not read any further than up to Section 12.3. You must however also read the other handout on the FANO algorithm. The flow-chart on Figure 6.46 is the most clear and the closest to that which you will implement.
Understanding Theta: One of the more complicated issues related to the algorithm is the use of the variable theta to implement the first visit check. Fano made the observation that a node is visited for the first time iff (a) it just satisfies the threshold, i.e., it violates the threshold tightened by delta or (b) it was entered via a forward move from a node, call it "node_b", that just satisfies the threshold itself. The Wozencraft and Jacobs book gives two examples of this that might be useful to study.
Case (a) corresponds to the situation that the threshold had to be loosened in order for this node to be able to be visited. The basic premise of the algorithm is that at each threshold value all paths that satisfy the threshold are explored. Consequently, we know that when the threshold is loosened to a point at which a node satisfies it, it will be visited before the threshold is loosened once again.
I *think* Case (b) corresponds to the case where node_b was visited for the first time and that the the visit to the current node occurs before the threshold is loosened once again. There are two subcases here. The first, Case (b.1), is where the threshold is not violated since the last move and the second, Case (b.2) is where the running threshold is violated. The second example in Wozencraft and Jacobs is an example of Case (b.2).
Based on these observations, we can see how theta works. Theta is set to one when the running threshold is violated. It is reset to 0, after a forward move to a node that just satisfies the threshold (Case (a)) OR from a node that just satisfied this threshold (Case (b.2)). For both of these cases, the threshold is tightened. Also, if the running threshold is not been violated then on a forward move theta is still 0 and in this case the current node must have been visited for the first time and threshold is tightened (Case b.1).