Methods and apparatus for frame detection

1. A frame detection circuit for detecting a frame boundary in a sequence of bits, the circuit comprising:

a first buffer for storing a first received frame of bits, wherein a width of the first buffer is a number of bits in one word in the sequence of bits;

a second buffer for storing a second received frame of bits, wherein a width of the second buffer is the number of bits in the one word; and

a staged-parallel structure of syndrome computation circuits that computes a number of syndromes in one cycle, wherein the number of the syndromes computed in one cycle is a fraction of the number of bits in the one word, and wherein each syndrome computation circuit in the staged-parallel structure has inputs consisting of a preceding syndrome, a head bit from the first received frame and a tail bit from the second received frame.

2. The frame detection circuit of claim 1 , wherein the positions of the head and tail bits are one frame length apart in the sequence of bits.

3. The frame detection circuit of claim 1 , wherein the preceding syndrome is based on a candidate frame beginning at the head bit.

4. The frame detection circuit of claim 3 , wherein each syndrome computation circuit computes a current syndrome which is based on a candidate frame beginning one bit after the head bit.

5. The frame detection circuit of claim 1 further comprising:

initial syndrome computation circuitry to compute an initial syndrome based on the first received frame.

6. The frame detection circuit of claim 1 further comprising, for each segment of a plurality of segments:

circuitry for reading a word of head bits from the first received frame; and

circuitry for reading a word of tail bits from the second received frame.

7. The frame detection circuit of claim 1 , wherein a number of the syndrome computation circuits in the staged-parallel structure is 2 n , where n is a counting number of two or more.

8. The frame detection circuit of claim 1 , wherein a maximum number of cycles needed to search for the frame boundary, after an initial syndrome computation, is a number of bits in a frame divided by a number of the syndrome computation circuits in the staged-parallel structure.

9. A method of detecting a frame boundary in a sequence of bits, the method comprising:

buffering a first received frame in a first buffer, wherein a width of the first buffer is a number of bits in one word in the sequence of bits;

buffering a second received frame in a second buffer, wherein a width of the second buffer is the number of bits in the one word; and

performing, by a staged-parallel structure of syndrome computation circuits, a plurality of syndrome computations in one cycle, wherein a number of the syndrome computations performed in one cycle is a fraction of the number of bits in the one word, wherein each syndrome computation circuit in the staged-parallel structure has inputs consisting of: a preceding syndrome; a head bit from the first received frame; and a tail bit from the second received frame.

10. The method of claim 9 , wherein the positions of the head and tail bits are one frame apart in the sequence of bits.

11. The method of claim 9 , wherein the preceding syndrome is based on a candidate frame beginning at the head bit.

12. The method of claim 9 , further comprising:

computing an initial syndrome based on the first received frame.

13. The method of claim 9 , wherein the plurality of syndrome computations is performed in segments, each segment including a number computations equal to a number of bits in one word.

14. The method of claim 13 further comprising, for each segment:

reading a word of head bits from the first received frame; and

reading a word of tail bits from the second received frame.

15. The method of claim 9 , wherein a number of the syndrome computation circuits in the staged-parallel structure is 2 n , where n is a counting number that is two or more.

16. The method of claim 9 , wherein a maximum number of cycles needed to search for the frame boundary, after an initial syndrome computation, is a number of bits in a frame divided the plurality of syndrome computations in one cycle.

17. A method of computing syndromes for detecting a frame boundary, the method comprising:

receiving a first word of head bits from a first buffer storing a first received frame;

receiving a second word of tail bits from a second buffer storing a second received frame; and

performing a cascaded sequence of syndrome computations using a series of cascaded computation stages, wherein each computation stage receives inputs consisting of corresponding head and tail bits from the first and second words and a preceding syndrome for a candidate frame beginning at the head bit, further wherein the corresponding head and tail bits are separated by one frame length.

18. The method of claim 17 , wherein each computation stage comprises a plurality of exclusive-or circuits, each exclusive-or generating a bit of the current syndrome.

19. The method of claim 18 , wherein each of the exclusive-or circuits receives at least a first input generated by multiplying the head bit by a corresponding bit from a first predetermined bit sequence, and a second input generated by multiplying the tail bit by a corresponding bit from a second predetermined bit sequence.

20. The method of claim 19 , wherein each of the exclusive-or circuits further receives a third input generated by multiplying a last bit of the preceding syndrome by a corresponding bit from a third predetermined bit sequence.

21. The method of claim 20 , wherein all but one of the exclusive-or circuits each further receives a fourth input comprising a shifted bit from the preceding syndrome.

22. The method of claim 1 , wherein the number of bits in one word is sixty-four, and wherein the number of syndrome computation circuits in the staged-parallel structure is four.

23. The method of claim 1 , wherein the number of bits in one word is sixty-four, and wherein the number of syndrome computation circuits in the staged-parallel structure is eight.