EM Algorithm 0 Flow

updated: 14-Apr-05

Steps in the algorithm are described in the table below. In the table

    Horizontal Vertical
Step Description Object Size SW Inputs Object Size SW Inputs
1 Add ICR 1 TT as needed 1 TT as needed
2.a ROI Sums 2x1 TTS:
0-8 x 0-7		 1x2 TTS:
0-7 x 0-8
2.b EM Iso Sums 2 (2x1) ROIs:
2-5 x 2-5		 2 (1x2) ROIs:
2-5 x 2-5
2.c HAD Sums 2x1 ROIs:
2-5 x 2-5		 1x2 ROIs:
2-5 x 2-5
3 ROI Compares 2x1 ROIs:
0-8 x 0-7		 1x2 ROIs:
0-7 x 0-8
4.a EM Iso
LM > 2a*Iso		 2x1 ROIs:
2-5 x 2-5		 1x2 ROIs:
2-5 x 2-5
4.b EM Frac
LM > 2b*HAD		 2x1 ROIs:
2-5 x 2-5		 1x2 ROIs:
2-5 x 2-5
5 AND Iso & EM Frac 1-bit 2-5 x 2-5 1-bit 2-5 x 2-5
6 Find Highest Thresh Passed 3-bits 2-5 x 2-5 3-bits 2-5 x 2-5
7 Choose H or V ROIs: 2-5 x 2-5
8 Make Output Words
(Thresh & Iso)		 EM: 2-5 x 2-5

Rules for Choosing Horizontal or Vertical Objects

Note: making this choice does not use an entire bunch crossing worth of latency (as previously assumed). It only takes one 90 MHz clock tick to choose which of the H or V threshold words to write to the output word.

Rules for making the choice are given below.

  1. For a given 2x2 region, if only one of the H or V ROIs produces a LM then choose that one.
  2. If both H and V LMs exist, choose the one with the highest Et.
  3. If Et(H) = Et(V) then consider the region to be Horizontal (needs to be discussed).
  4. The Isolation bit corresponding to the H or V ROI chosen is output.

An important question is at what point in the algorithm to choose between the Horizontal and Vertical ROIs in a given 2x2 region. It turns out that latency is minimized if the choice is made just before writing threshold words for each ROI to the output word. So that is what we have decided on.

The following are also possible, but would cost a full BC in latency, and therefore disfavored.

  1. Choose after step 2 based on rules 1 and 2 above. highest Et.
  2. Choose the H or V LM remaining after step 3, or if both H and V LMs exist for a 2x2 region, use rules 1 and 2 above.