Abstract:
Apparatus and method extract data from a data stream. The method includes oversampling the data stream, performing first processing on adjacent bits of the oversampled data stream, performing second processing the results of the first processing, comparing the results of the second processing, and selecting an alignment of data based on the comparison. The method can be efficiently implemented using accumulators, delay elements, and XOR elements. In this manner, data may be extracted from the data stream despite a varying or unknown phase or duty cycle, or in the presence of jitter.

Description:
CROSS-REFERENCES TO RELATED APPLICATIONS 
   Not Applicable 
   STATEMENT AS TO RIGHTS TO INVENTIONS MADE UNDER FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
   Not Applicable 
   REFERENCE TO A “SEQUENCE LISTING,” A TABLE, OR A COMPUTER PROGRAM LISTING APPENDIX SUBMITTED ON A COMPACT DISK. 
   Not Applicable 

   BACKGROUND OF THE INVENTION 
   A data stream is often conceptualized as consisting of discrete values. For example, a binary data stream may be represented by the symbols {1, −1} or {1, 0}. The data stream would then be conceptualized as a string of binary symbols, for example, 10001110100101. 
   However, in the real world, the data stream is in actuality an analog representation of the discrete values. Extracting the discrete values from the analog data stream can be difficult, especially when the phase and duty cycle of the data stream are varying or unknown. Jitter can also negatively impact accurate data extraction. 
   Programmable logic devices (PLDs) are integrated circuit devices that often include input/output (I/O) components, memory components, and processing components (such as microprocessors and digital signal processors [DSPs]) in configurable arrangements. A particular PLD, then, may be configured in many different ways that each correspond to a different application. Thus, a data stream received by a PLD may come from a variety of sources, the variety being a function of the wide variety of different applications. 
   There is a need for a device that accurately extracts discrete values from a data stream. There is a need for such a device that can respond flexibly to a variety of data streams resulting from a wide variety of PLD implementations. There is a need for such a device that is quick, is efficient, and may be implemented with a small number of components. 
   BRIEF SUMMARY OF THE INVENTION 
   Embodiments of the present invention are directed toward extracting data from a data stream that may have an unknown or varying phase or duty cycle, or that may have jitter. 
   According to an embodiment of the present invention, a method extracts data from a data stream. The method includes oversampling the data stream at an oversampling rate and generating data samples. The method further includes processing the data samples and generating first results, wherein the data samples are processed such that two or more adjacent data samples are processed together, and wherein the number of adjacent sampled processed together corresponds to the oversampling rate. The method further includes processing the first results over time and generating second results, wherein each of the first results is processed with others of the first results such that the number of second results corresponds to the oversampling rate. The method further includes analyzing the second results and selecting an alignment of the data samples according to one of the second results. 
   According to another embodiment of the present invention, an apparatus extracts data from a data stream. The apparatus includes an oversampler, a first group of processing elements, a second group of processing elements, and a comparator element. These elements perform as described above regarding the method. 
   According to another embodiment of the present invention, a method extracts data from a data stream. The method is similar to the method described above, with the addition of processing a set of data samples according to a mirror axis of the set. 
   According to another embodiment of the present invention, an apparatus extract data from a data stream. The apparatus is similar to the apparatus described above, with the addition of processing a set of data samples according to a mirror axis of the set. 
   According to another embodiment of the present invention, a programmable logic device includes function blocks, an interconnect, and a data extractor circuit as described in the embodiments above. 
   According to embodiments of the present invention, the number of processing elements corresponds to the oversampling rate. 
   In this manner, data may be extracted from the data stream despite a varying or unknown phase or duty cycle, or in the presence of jitter. 
   A fuller description of the embodiments of the present invention is provided with reference to the following drawings and related description. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a block diagram of a PLD that includes a data extractor according to an embodiment of the present invention. 
       FIG. 2  is a block diagram of a data extractor according to an embodiment of the present invention. 
       FIG. 3  is a block diagram of a first stage in the data extractor of  FIG. 1  according to an embodiment of the present invention. 
       FIG. 4  is a block diagram of a second stage in the data extractor of  FIG. 1  according to an embodiment of the present invention. 
       FIG. 5  is a block diagram of a data extractor according to an embodiment of the present invention. 
       FIG. 6  is a block diagram of a first stage in the data extractor of  FIG. 5  according to an embodiment of the present invention. 
       FIG. 7  is a block diagram of a first stage in the data extractor of  FIG. 5  according to an embodiment of the present invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 1  is a block diagram of a PLD  100  according to an embodiment of the present invention. The PLD  100  includes numerous function blocks  102 , an interconnect  104 , and various input and output interfaces (not shown). The function blocks  102  perform various functions, such as memory, signal processing, input/output, microprocessing, etc. The interconnect  104  connects the various function blocks  102  to each other and to the input and output interfaces. A user may then configure the PLD to perform various functions according to which function blocks  102  are selected for use and how the selected blocks are connected via the interconnect  104 . 
   The PLD  100  also includes a data extractor  106 . (The data extractor may also be considered to be an input interface to the PLD  100 .) The data extractor  106  extracts data from an input data stream  108  and provides the extracted data to the components of the PLD. 
   Because of the wide variety of applications in which the PLD  100  may be used, and imperfections in the generation and transmission of the various signals connected to the PLD, the input data stream  108  may vary widely from an ideal data stream. The input data stream  108  may have an unknown or varying phase and/or duty cycle, and may contain jitter. The data extractor  106  works to overcome these issues in the wide variety of implementations of the PLD  100 . 
     FIG. 2  is a block diagram of a data extractor  106  a according to an embodiment of the present invention. The data extractor  106  a includes an oversampler  110 , a first stage  112 , a second stage  114 , and an analyzer  116 . 
   The oversampler  110  oversamples the input data stream  108  at a designated oversampling rate. For example, if the input data stream  108  has an expected rate of 1 Mbps, and 3= oversampling is desired, the oversampler  110  generates the output data  111  at a rate of 3 Mbps. In such a case, each “bit” of the input data stream  108  is represented by three “bits” of the output data  111 . 
   The first stage  112  performs a first processing step on the output data  111  from the oversampler  110 . The first stage  112  is further detailed below with reference to FIGS.  3  and  6 - 7 . In general, the first stage  112  includes a number of accumulator elements that corresponds to the oversampling rate. The first stage  112  outputs intermediate accumulation results  113 . 
   The second stage  114  performs a second processing step on the output  113  from the first stage  112 . The second stage  114  is further detailed below with reference to FIG.  4 . In general, the second stage  114  includes a number of accumulator elements that corresponds to the oversampling rate. The second stage  114  outputs final accumulation results  115 . 
   The analyzer  116  performs analysis in the final accumulation results  115  and selects the desired alignment of the input data stream  108  based on the analysis. In general, the desired alignment is the one with the highest final accumulation result from the second stage  114 . Once the analyzer  116  has determined the desired alignment for the input data stream  108 , the data bits corresponding to that alignment may be provided to the other components of the PLD  100 . The data bits may be tapped from a desired point in the data extractor  106   a , such as from the output  111  of the oversampler  110  or from an internal point in the first stage  112  (see  FIG. 3  for more details). 
   As an example, consider the input data stream D being oversampled, generating the sampled stream B. B consists of elements b t ={+1, −1}, using t as the index to indicate the t th  bit of the sample stream. (Note that +1 and −1 are “logical” values that may also be represented as the “digital” values 0 and 1. ) If the sample stream is ideal, it would always contain n matching bits, where n is the oversampling factor. If the oversampling factor is 3, for example, bits b 0 , b 1  and b 2  should be identical; bits b 3 , b 4  and b 5  should be identical, etc. The oversampled stream could be:
 
+1+1+1−1−1−1−1−1−1+1+1+1−1−1−1 . . .
 
for the data message:
 
+1 −1 −1 +1 −1 . . .
 
   In this example, it does not matter where data is sampled. In read systems, however, there are a number of error sources, including phase jitter and duty cycle variations. The sampled data stream could then look as follows:
 
+1+1+1+1−1−1−1−1+1+1+1+1+1−1+1 . . .
 
   In this case, it is important to sample the datastream at the correct time to extract the data message. If the message was extracted from bits  1 ,  4 ,  7 , . . . , etc. we could get a different message than we would if we extracted the message from samples  2 ,  5 ,  8 , . . . , etc. or  3 ,  6 ,  9 , . . . , etc. The task of the synchronization circuit  106  is to find which set of samples is the best set to extract the data message from, without any prior knowledge of what the data message is. 
     FIG. 3  is a block diagram of an embodiment  112   a  of the first stage  112  (see FIG.  2 ). The first stage  112   a  is designed for an oversampling rate of three. The first stage  112   a  includes four delay stages  120   a ,  120   b ,  120   c  and  120   d , and three accumulator stages  122   a ,  122   b  and  122   c . The oversampled data stream  111  is the input and the intermediate accumulation result  113  is the output. The delay stages  120  delay the oversampled data stream  111  such that each of the accumulators  122  sees a set of three adjacent samples. The accumulators  122  accumulate the results of sets of three adjacent samples. The first stage  112   a  may be used when the duty cycle is known to be correct, but the phase is unknown, and there may be phase jitter. 
   To find the best synchronization, n summation units  122  are used in the first stage, which all accumulate n samples over time. Their start points are offset by one sample each. Using the example with oversampling factor n=3: 
   1. Accumulator  122   a  adds together b 0 , b 1  and b 2 , providing its first intermediate accumulation result  113   a . It will then accumulate b 3 , b 4  and b 5  for its second result  113   a , etc. 
   2. Accumulator  112   b  adds together b 1 , b 2  and b 3  for its first intermediate accumulation result  113   b , then accumulate b 4 , b 5  and b 6  for its second result  113   b , etc. 
   3. Accumulator  112   c  adds together b 2 , b 3  and b 4  for its first intermediate accumulation result  113   c , then accumulate b 5 , b 6  and b 7  for its second result  113   b , etc. 
   In general, the n th  first stage accumulation for the t th  data bit will be: 
         accu1     n   ,   i       =       ∑     i   =   0       n   -   1       ⁢           ⁢       b   n     ⁢     ·     t   +   i   +   n   -   1               
 
   The results will be +3 (that is, +1, +1, +1) and −3 (that is, −1, −1, −1) for the best synchronized of the n samples in the example, or {+n, −n} in general. For the others, it will be +3 and −3 if two consecutive data bits match, and lower values if they do not. 
   The data bits may be tapped from any desired point in the first stage  112   a , such as from the input  111  or from an output from one or more of the delay stages  120 . 
     FIG. 4  is a block diagram of an embodiment  114   a  of the second stage  114  (see FIG.  2 ). The second stage  114   a  is designed for an oversampling rate of three. The second stage  114   a  includes three accumulator stages  130   a ,  130   b  and  130   c  and an overflow control circuit  132 . The intermediate accumulation results  113  are the input and the final accumulation results  115  are the output. The accumulator stages  130   a ,  130   b  and  130   c  accumulate the respective intermediate accumulation results  113   a ,  113   b  and  113   c . The overflow control circuit  132  keeps the accumulator stages  130  from overflowing. 
   In the second stage  114   a , the signs of the intermediate accumulation results  113  are removed, and then the intermediate results are accumulated again, using a second set of n accumulators. The results may be represented by the following formula: 
         accu2   n     =       ∑     t   =   0     ∞     ⁢           ⁢     accu1     n   ,   t             
 
   Of this second set, one accumulator  130  will add n to its current value. The index of this accumulator  130  indicates the best alignment of the input data stream. The other accumulators  130  will add a number that is between 0 and n, depending on the oversampling factor and whether the bits in the data stream  111  match their neighbors. The accumulation result  115 , assuming that at least one data bit does not match its predecessor, is therefore smaller than the result in the accumulator that is best aligned. Even if all databits were equal, the correct data message would be chosen, because synchronization would not matter. 
   The overflow control circuit  132  monitors the accumulators  130  and keeps them from overflowing. The overflow control circuit can do so in numerous ways, as desired according to the particulars of the implementation. One implementation of the overflow control circuit  132  is to deduct the value of the smallest accumulator from all the accumulators at every step or at another interval. Another implementation is to deduct a constant value from all accumulators if any accumulator exceeds a set threshold. Still another implementation is to accumulate n−x instead of n (that is, to accumulate n minus the number of matches instead of accumulating the number of matches, where x is the number of matches). That way the maximum in the highest accumulator would be zero, and all other accumulators would contain negative numbers, and clipping would be used. 
     FIG. 5  is a block diagram of a data extractor  106   b  according to another embodiment of the present invention. The data extractor  106   b  is similar to the data extractor  106   a  (see  FIG. 2 ) with a different first stage (first stage  140  in  FIG. 5  versus first stage  112  in FIG.  2 ). Otherwise the operation is similar. The embodiment of  FIG. 5  is useful when the phase is unknown, there may be phase jitter, and the duty cycle is unknown (as compared to the embodiment of  FIG. 2 , which is useful when the duty cycle is known). 
   Using an example with an oversampling factor of  3 , if the first stage accumulator sees (+1+1+1) or (−1−1−1), this is a good indication that the accumulator is aligned to the data stream, whereas patterns such as (+1+1−1), (−1−1+1), (+1−1−1) and (−1+1+1) indicate that the accumulator is not aligned. Special cases are the patterns (+1−1+1) and (−1+1−1). These patterns occur when the phase is correct and the accumulator is aligned, but the duty cycle is wrong. Hence these patterns also represent correct alignment. 
   The process may be described as finding the mirror axis for each symbol. When previous samples match next samples belonging to the same symbol, the mirror axis is found, and the synchronization is improved. 
   In general for the first stage  140  with oversampling factor n, where n is an odd number, the following equation gives the results: 
         accu1     n   ,   t       =       ∑     i   =   1         (     n   -   1     )     /   2       ⁢           ⁢       b   n     ⁢     ·     t   +   i       ·     b   n     ⁢     ·     t   -   i               
 
   Where n is an even number, the following equation gives the results: 
         accu1     n   ,   t       =       ∑     i   =   1       n   /   2       ⁢           ⁢       b   n     ⁢     ·     t   +   i       ·     b   n     ⁢     ·     t   -   i   +   1               
 
   The disadvantage of using an even number of samples per data bit is that in the ideal case, two accumulators will have the same result, and the ideal sample point would be in the middle between the two. 
   Note that the equations in the above description deal with the mathematical representation of the signal, that is {+1, −1}. In digital logic, the representation of the signal may be {0, 1}. Multiplications may then be performed by XORs, making the structure efficient to implement in digital logic. 
     FIG. 6  is a block diagram of the first stage  140   a  according to one embodiment of the present invention, for an oversampling factor of 3. The first stage  140   a  includes three XOR blocks  142   a ,  142   b  and  142   c , and flour delay stages  144   a ,  144   b ,  144   c  and  144   d . Thus, the XOR block  142   a  provides the results for b 0 *b 2 , b 3 *b 5 , b 6 *b 8 , etc. 
     FIG. 7  is a block diagram of the first stage  140   b  according to another embodiment of the present invention, for an oversampling factor of  5 . The first stage  140   b  includes a delay matrix  150 , ten XOR blocks  152   a-   152   j , and five accumulators  154   a-   154   e . The delay matrix  150  delays the output data  111  and generates a plurality of delayed output data  111   b . Each element in the delayed output data  111   b  is the output data delayed by one or more oversampled periods. These elements are then provided to the appropriate ones of the XOR blocks  152   a-   152   j  in order to implement the above equation. Thus, the first accumulator  154   a  provides the results for b 0 *b 4+ b 1 *b 3 , b 5 *b 9+ b 6 *b 8 , etc. (The delay matrix  150  may be implemented as individual delay blocks as in  FIG. 6  if so desired.) 
   Although the above description has focused on specific embodiments, it is to be understood that numerous modifications, additions, changes and variations may be performed without departing from the scope of the present invention, which is defined by the following claims.