Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
1999-08-19
2003-12-02
Marcelo, Melvin (Department: 2739)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
C370S514000
Reexamination Certificate
active
06658026
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method in connection with serial data transfer to recognize a fixed synchronization bit pattern.
Although the present invention has been developed in connection with the V.110 protocol, it is to be understood that the general principle of the invention can also find its application in connection with similar systems.
BACKGROUND OF THE INVENTION
For serial data transfer with rate adaption a commonly used protocol is the V.110. When developing equipment for this protocol one will be faced to the problem of how to recognize the V.110 frame synchronization pattern. One can choose to solve it either in hardware, software or by a combination of both hardware and software. Often the hardware solution is preferred because the software alternative is considered to take too much of the CPU-capacity. However, with the present algorithm the sync-detection is quite easy to handle in software. Compared to the rest of the V.110 processing that usually is done in software, this extra load is very small.
Before the present method or algorithm is described, reference should be made to
FIG. 1
illustrating how the 80 bits V.110 frame appears. Octet zero contains all binary 0, whilst octet
5
consist of binary 1 followed by seven E bits. Octets
1
-
4
and
6
-
9
contain a binary 1 in bit number one, a status bit (S- or X-bit) in bit number
8
and six data bits (D-bits) in bit positions
2
-
7
. The order of bit transmission is from left to right and top to bottom.
The 17 frame synchronization bits (*) consist of all eight bits set to binary 0 in octet zero and a binary 1 in bit position
1
in the following nine octets. Through this document special attention should be focused on these synchronization bits (*)
At a first glimpse the finding of the synchronization pattern may be considered as quite easy. This would, it is true, obviously be easy if the ten octets always arrive byte-aligned in the computer memory in question. But here is where the problem starts.
When the serial bit stream “ticks” into the receive-buffer in the computer memory, one has no guarantee that the octets in the frame fall into corresponding byte-addressable locations.
FIG. 2
illustrates how odd the serial bit stream may arrive in a byte-addressable computer memory store. Consequently, the V.110 frame octets included in the bit stream appearing in
FIG. 2
will not necessarily be byte-aligned as compared with FIG.
1
. Hence, each octet may be split between or partly cover two consecutive addresses as regards byte-alignment.
PRIOR ART
From U.S. Pat. No. 5,204,883 (Blanc) there is known a method and an apparatus for recognition of a framing pattern distributed in a serial bit stream. The framing pattern comprises M single bits distributed at intervals of a fixed number, N of bits, as measured from the start of one framing bit to the start of the next, in an incoming serial bit stream. The prior art system makes a computation following each reception of an arbitrary group of N incoming data, and will after a minimum number of computation steps to distinguish between a ‘look alike’ framing pattern and a ‘true’ framing pattern, point out with no ambiguity the very position of the ‘true’ pattern within the bit stream, thus allowing synchronization over that stream.
This prior art describes a method for synchronizing in relation to a bit pattern, wherein each individual bit in the pattern is distributed with randomly arranged user data therebetween.
However, this prior art technique is silent about finding a bit pattern which is not “bit-distributed”, and would consequently not be able to use for the recognition of such bit patterns.
U.S. Pat. No. 5,177,738 (Dell'Oro et al.) discloses a process and a monolithically integrated device for speed adaption for integrated services digital networks (ISDN), which process relates to synchronizing and decomposing asynchronous data frames of different lengths of a serial bit stream structured in octet-rows of bits containing frame synchronization bits and data bits, for rate adaption of synchronous and asynchronous terminals of said ISDN during data reception from said network.
EP 0 727 886-A2 (Anderson/Wandel & Golterman Technologies Inc.) discloses a method related to digital data sequence pattern filtering, which method is octet/byte oriented. In practice this will involve that the method is operated on a byte stream, and that a byte alignement can be assumed.
However, this prior art does not give any instructions about a method related to a bit stream, let alone any solution to the problem enfaced with not being byte aligned in relation to the bit pattern to be recognized.
U.S. Pat. No. 5,412,754 (Newley et al.) relates to a pattern recognizing system, comprising a transmitter and receiver for transmitting and receiving a serial stream of bits that includes data bits and a predetermined bit pattern, the system being adapted for recognizing said bit pattern. The system checks each received bit and compares this with the state value of previous bits until the predetermined bit pattern is recognized. This system is a slow system since it requires a comparison or checking operation for each received bit. In other words, this system is silent about conducting a comparison or checking operation only for each 8th received bit.
U.S. Pat. No. 5,412,610 (Suzuki) relates to a serial data transfer device, wherein serial data are transfered to/from an FIFO buffer. However, there is no information in this publication concerning how a special bit pattern can be recognized in such a buffer, for example data which have been received from a serial communication link.
In conclusion, none of the cited references give any instructions regarding how to recognize a synchronization pattern in a frame according to V.110 protocol, let alone that this recognition can be effected by a fast search algorithm for such V.110 synchronization pattern.
SUMMARY OF THE INVENTION
The main object of the present invention is to provide a fast search algorithm for V.110 synchronization pattern.
It is also an object of the invention to provide a fast search algorithm for a FAX application in which the aim is to recognize eleven zeros (0) followed by a single one (1) in a bit stream (known as EOL, i.e. End-Of-Line).
Another object of the present invention is to provide an appropriate CheckBitMaskTable to be used in connection with such a fast search algorithm.
A further object of the present invention is to provide an algorithm in which two arbitrary bit groups or bytes are compared with each other and the result thereof compared with further criteria given by the V.110 frame.
Still another object of the present invention is to provide an algorithm which is easy to handle in software, and which represents only a very small load compared with the related processing in software.
Yet another object of the invention is to provide an algorithm for finding a bit pattern which is not bit distributed.
A still further object of the invention is to provide an algorithm conducting a comparison or checking operation only for each 8th received bit in a bit stream and thereby increasing the speed at which the algorithm can operate.
BRIEF DISCLOSURE OF THE INVENTION
The above objects are achieved in connection with a method as stated in the preamble, which according to the invention is characterized by examining two successive elements, by performing a binary AND operation between the first element and a check element made up from the second element, then examining if the binary AND operation is zero for thereafter establishing whether said first element and second element qualify as candidates for the synchronization pattern, and further verifying said candidates by checking further criteria given by the frame in question.
Further features and advantages given by the present invention will appear from the following description taken in conjunction with the enclosed drawings and appendices, as well as from the enclosed patent claims.
REFERENCES:
patent: 5177738 (1993-01-0
Marcelo Melvin
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method in connection with serial data transfer to recognize... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method in connection with serial data transfer to recognize..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method in connection with serial data transfer to recognize... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3104505