CROSS-REFERENCE TO PRIOR APPLICATIONS

[0001] This application claims priority of U.S. Patent Application No.

62/084,394, filed on November 25, 2014, which is all hereby incorporated by reference in its entirety.

BACKGROUND

A. Technical Field

[0002] The present invention relates to signal processing, and more particularly, to systems and methods for detecting peaks of signals in a continuous data stream.

B. Background of the Invention

[0003] Various techniques for detecting peaks of signals in a continuous data stream have been developed in the past decades. For instance, ultra-wide band (UWB), which is a radio technology, is used at a very low energy level for short-range, high- bandwidth communications using a large portion of the radio spectrum. Recently, UWB has been applied to collect target sensor data, locate and track target sensors with high precision. A receiver of UWB signals/pulses that are transmitted by a UWB transmitter should be able to detect/identify the UWB signals in a continuous data stream that is typically mixed with noise. To identify the UWB signals, the receiver should be able to detect the peaks of the UWB signals. [0004] In some applications, the pulse widths of UWB signals may decrease to the order of nanosecond. As such, techniques for detecting the UWB signals should be carefully designed to capture the peaks of short UWB signals and differentiate the desired signals from noise. Another challenge that a signal processing engineer has to cope with is associated with multipath reflections of a strong pulse in the digital domain. For instance, when a transmitter transmits a UWB signal, the signal may be reflected by objects before it arrives at a receiver. As such, when an incoming signal is reconstructed/represented by the receiver in the digital domain, the reflected signals (or, equivalently, multipath reflections) may be superimposed onto the direct UWB signal. As a first step to differentiate the desired signal from the multipath reflections and/or other noise, it is necessary to detect/identify peaks of the desired signals in the continuous data stream. Thus, there is a need for a method for detecting the peaks of signals in a continuous data stream.

Summary of the invention

[0005] In one aspect of the present invention, a method for detecting a peak of a ultra- wide-band (UWB) signal in a data stream includes: selecting a portion of a data stream in a current clock cycle, the portion of the data stream includes a preset number of data samples; finding a set of data samples included in the preset number of data samples, the set of data samples includes one or more consecutive data samples and has a uniform magnitude; and promoting the set of data samples as a peak if the uniform magnitude is higher than a magnitude of a first data sample that immediately precedes the set of data samples and a magnitude of a second data sample that immediately follows the set of data samples.

[0006] In another aspect of the present invention, a system for detecting a peak of an ultra-wide-band (UWB) signal in a data stream includes: one or more processors; and a non-transitory computer-readable medium or media comprising one or more sequences of instructions which, when executed by the one or more processors, causes steps to be performed comprising: selecting a portion of a data stream in a current clock cycle, the portion of the data stream includes a preset number of data samples; finding a set of data samples included in the preset number of data samples, the set of data samples includes one or more consecutive data samples and has a uniform magnitude; and promoting the set of data samples as a peak if the uniform magnitude is higher than a magnitude of a first data sample that immediately precedes the set of data samples and a magnitude of a second data sample that immediately follows the set of data samples.

Brief Description of the Drawings

[0007] References will be made to embodiments of the invention, examples of which may be illustrated in the accompanying figures. These figures are intended to be illustrative, not limiting. Although the invention is generally described in the context of these embodiments, it should be understood that it is not intended to limit the scope of the invention to these particular embodiments.

[0008] FIGS. 1A and IB show data sampling windows applied to a continuous data stream to detect peaks according to one embodiment of the present invention.

[0009] FIG. 2 shows a data sampling window applied to a continuous data stream to detect peaks according to one embodiment of the present invention.

[0010] FIGS. 3 A - 3D show exemplary samples having concave patterns according to one embodiment of the present invention.

[0011] FIGS. 4 A - 4C show exemplary samples having convex patterns according to one embodiment of the present invention.

[0012] FIGS. 5A - 5D show exemplary samples having monotonic up (rising) patterns according to one embodiment of the present invention. [0013] FIGS. 6 A - 6C show exemplary samples having monotonic down (falling) patterns according to one embodiment of the present invention.

[0014] FIG. 7 shows exemplary samples having a constant pattern according to one embodiment of the present invention.

[0015] FIG. 8 shows a waveform subject to filtering according to one embodiment of the present invention.

[0016] FIG. 9 shows a constant waveform that is not subject to filtering according to one embodiment of the present invention.

[0017] FIG. 10 shows a computer system according to embodiments of the present invention.

[0018] FIG. 11 shows a schematic diagram of an exemplary system for transmitting and receiving UWB signals according to one embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0019] In the following description, for the purposes of explanation, specific details are set forth in order to provide an understanding of the invention. It will be apparent, however, to one skilled in the art that the invention can be practiced without these details. One skilled in the art will recognize that embodiments of the present invention, described below, may be performed in a variety of ways and using a variety of means. Those skilled in the art will also recognize additional modifications, applications, and embodiments are within the scope thereof, as are additional fields in which the invention may provide utility. Accordingly, the embodiments described below are illustrative of specific embodiments of the invention and are meant to avoid obscuring the invention.

[0020] A reference in the specification to "one embodiment" or "an embodiment" means that a particular feature, structure, characteristic, or function described in connection with the embodiment is included in at least one embodiment of the invention. The appearance of the phrase "in one embodiment," "in an embodiment," or the like in various places in the specification are not necessarily all referring to the same embodiment.

[0021] Furthermore, connections between components or between method steps in the figures are not restricted to connections that are effected directly. Instead, connections illustrated in the figures between components may be modified or otherwise changed through the addition thereto of intermediary components, without departing from the teachings of the present invention.

[0022] FIGS. 1A and IB show data sampling windows 104 and 114 applied to a continuous data stream 102 to detect peaks according to one embodiment of the present invention. As depicted in FIG. 1A, four samples, 00, 01, 02, and 03, are simultaneously taken in each clock cycle, i.e., the electronic hardware/algorithm may "see" the continuous data stream (or, equivalently waveform) as one four-sample window of samples at a time. It is noted that any suitable number of samples may be taken simultaneously in each clock cycle. For instance, the four-sample window may be extended to an eight-sample window. Likewise, the electronic hardware/algorithm may see the waveform as two or more four- sample windows of samples at a time. In the present application, for brevity, only one four- sample window is considered in detecting peaks on the waveform 102 in each clock cycle.

[0023] "Looking Glass" problem: The primary challenge of the peak-detector implementation may be that the samples observed in any given clock cycle are finite, while the determination of whether a given sample is to be "crowned" as a peak depends on previous samples as well as future samples. FIGS. 1A and IB illustrate a case in which the knowledge of future samples is necessary to resolve whether the sample A is a peak.

[0024] As depicted in FIGS. 1A and IB, the sample A may be identified as a "candidate peak" in the n* clock cycle, but it's not until the following clock cycle that the algorithm can determine with certainty that sample A is indeed a peak. The data from the n* clock cycle is gone in (η+1) ^Λ clock cycle, and thus, there is need to store information from the past for properly identifying peaks in the "future." This type of identification is referred to as forward checking or backward peak nomination.

[0025] Another interesting case of the "Looking Glass" is when a sample in the current frame can be "crowned" as a peak only if certain conditions in the previous frame allow it. FIG. 2 shows a data sampling window 204 applied to a continuous data stream 202 to detect peaks according to one embodiment of the present invention. As depicted, at a given clock cycle, the sample B can be "nominated" as a peak, but only if the algorithm can examine the sample B from the window observed in the preceding clock cycle. This type of identification is referred to as backward checking or forward peak nomination.

[0026] "Sample classification: When processing the sample stream through the "Looking Glass," the samples that are peaks or candidate -peaks may be classified as follows: (1) Definite Peak (DP): DP is marked as a solid circle, such as sample A in FIG. 3 A. DP is an unambiguous peak sample and will be time-stamped. (2) Forward Check (FC) candidate: FC is marked as a dashed circle, such as sample D in FIG. 3C. FC is a sample that might be promoted (or demoted) to being a peak, in a later window, but the information obtained in the current sample window is not sufficient to determine whether it is a peak. (3) Backwards Check (BC) candidate: BC is marked as an incomplete circle, such as sample E in FIG. 3D. BC is a sample that may be promoted (or demoted) to being a peak, based on some past information. In the present application, the magnitudes of the samples in the current four- sample window are defined in a binary notation, CM00, CMOl, CM02, and CM03, where the "older" sample is CM00 and the "newer" sample is CM03. Also, the notation PM03 denotes the last (newer) sample in the preceding four-sample window.

[0027] Window pattern classification: The "Looking Glass" window allows examination of four consecutive samples at a time. For convenience, the observed patterns of the four samples are classified and defined as follows:

[0028] (1) Concave (wave-like) shape/pattern: This class of shapes includes those sets of four sample windows which have a form of concavity or wave-like shape. FIGS. 3A - 3D show exemplary samples having concave shapes according to one embodiment of the present invention. As depicted, each of FIGS. 3A - 3D shows four samples having a concave pattern and a DP.

[0029] The DPs (i.e., samples A, B, C and F) in FIGS. 3 A - 3D are determined as such since the conditions for peak within the same window of samples can be identified without information of samples in the past or later window. The sample D in FIG. 3C is a FC candidate because it may be promoted (or demoted) to a peak in a later window but the information obtained in the current sample window is not sufficient to determine whether it is a peak. The sample E is a BC candidate since it may be promoted (or demoted) to a peak based on the information of the samples taken in the preceding window.

[0030] The conditions for deciding if a sample is DP, FC or BC in the current window can be expressed as following equations:

DP = ((CMOl > CM00 ) AND (CMOl > CMOl ) ) OR

((CMOl > CM00 ) AND (CMOl = = CMOl ) AND (CMOl > CM03 ) ) OR

((CM02 > CMOl ) AND (CMOl > CM03 )) ( 1 )

BC = (CM00 > CMOl ) AND ((FC < CM00) OR (PM03 < CM00)) (2)

FC = (CM03 > CM02) (3)

[0031] (2) Convex shape/pattern: This class of shapes includes those sets of four sample windows which have a convex like form. FIGS. 4A - 4C show exemplary samples having convex patterns according to one embodiment of the present invention. In each of the four windows shown in FIGS. 4A - 4A, the first sample may be a BC while the last sample may be a FC.

[0032] The conditions for deciding if a sample is DP, FC or BC in the current window can be expressed as following equations:

DP = 0 (4)

BC = ((CM00> CMOl ) OR ((CM00= = CMOl ) AND (CMOl > CMOl ) ) ) AND

((FC<CM00 ) OR (PM03 < CM00 )) (5)

FC = ((CM03>CM01) OR ((CM01>CM01 ) && (CM01==CM03)) (6)

[0033] (3) Monotonic up pattern: This class of shapes includes those sets of four sample windows which have a monotonic up (rising) shape. FIGS. 5A - 5D show exemplary samples having rising patterns according to one embodiment of the present invention. [0034] The conditions for deciding if a sample is DP, FC or BC in the current window can be expressed as following equations:

DP = 0 (7)

BC = 0 (8)

FC = ((CM03>CM02 ) OR

((CM02 > CMOl ) AND (CM02 = = CM03 ) ) OR

( ( CMOl > CM00 ) AND (CM01 ==CM02) && (CM02==CM03)) (9)

[0035] (4) Monotonic down (falling) pattern: This class of shapes includes those sets of four sample windows which have a monotonic down (falling) pattern. FIGS. 6A - 6C show exemplary samples having falling patterns according to one embodiment of the present invention.

[0036] The conditions for deciding if a sample is DP, FC or BC in the current window can be expressed as following equations:

DP = 0 (10)

BC = ( (CM00> CMOl ) OR

((CM00= = CMOl ) AND (CMOl > CM02 ) ) OR

((CM00= = CMOl ) AND (CMOl = = CM02 ) & & (CM02 > CM03 ) )

) AND

((FC<CM00 ) OR (PM03 < CM00 )) (11)

FC = 0 (12)

[0037] (5) Constant pattern: This pattern includes those sets of four sample windows which have a constant magnitude. FIG. 7 shows exemplary samples having a constant pattern according to one embodiment of the present invention. [0038] The conditions for deciding if a sample is DP, FC or BC in the current window can be expressed as following equations.

DP = 0 (13)

BC = 0 (14)

FC = ((CM00= = CMOl ) AND (CMOl = = CM02 ) AND (CM02 = = CM03 ) )

AND ((FC<CM00) OR (PM03<CM00)) (15)

[0039] Table 1 shows the list of equations based on the different pattern classifications, where the equations derived for each class are combined into a single equation per type of peak.

Table 1. Consolidated equations for DP, FC, and BC

[0040] Promotion and demotion of FC and BC samples: The FC and BC samples are just candidates for being peaks. The determination whether an FC sample is to be a peak or is to be ignored depends on future information. The determination whether a BC sample is to be a peak or to be ignored depends on past information. The determination whether an FC or BC sample is to be a peak is referred to as "promotion" and the determination whether an FC or BC sample is not to be a peak as "demotion".

[0041] For BC type samples, the promotion/demotion is immediate and follows directly from Table 1, and, when the conditions are met, a BC sample will only be in index 00. For FC type samples, the promotion (or demotion) happens in a future sample window

(may not be the immediate sample window where the FC was first identified).

[0042] For a given sample window, if an FC was previously set, a promotion to a peak will be made if one of the following conditions are met:

FC is promoted if and only if FC exists AND:

(FC>CM00) OR

((FC==CM00) AND (FC>CM01)) OR

((FC==CM00) AND (CM00==CM01) (CM01>CM02)) OR

(FC==CM00) AND (CM00==CM01) AND (CM01==CM02) AND (CM02>CM03)

OR

TIMEOUT on constant waveform

[0043] An FC is not updated if, and only if the FC sample has a "constant" pattern, and the FC is equal to the magnitude of the samples in the current window:

FC remains unmodified if and only if:

(FC==CM00) AND (CM00==CM01) AND (CM01==CM02) AND (CM02==CM03) No timeout this window

[0044] An FC is demoted if and only if the following conditions are met: FC demoted if and only if:

(FC exists) AND NOT ((FC promotion) OR (FC remains unmodified))

[0045] Masking samples after a peak is detected: Typically, a continuous data stream includes desired signal mixed with irrelevant noise, where, without proper filtering mechanisms, the noise may result in too many peaks. Thus, it is desirable to have a programmable duration, after the detection of a peak, during which no additional peaks are to be detected. In embodiments, this duration may depend on the magnitude of the previously detected peak, i.e., a magnitude-based-filtering may be applied. For instance, the maximum magnitude of a peak may be divided into eight levels and the actual peak magnitude will be compared to the eight levels for determination of the number of "filtered" samples. Table 2 shows eight levels of the peak magnitudes and the filtering durations for the eight levels, where the respective DLYMAGx (delay-based-on-magnitude) are programmable, eight-bit register fields. Table 3 shows eight levels of the peak magnitudes and exemplary filtering durations in the unit of samples to be ignored and not time stamped. For instance, when a detected peak has the magnitude of seven, the peaks in the following seven samples are ignored and not time stamped. It is noted that the peak magnitudes in Tables 2 and 3 may be divided into any suitable number of levels and the filtering durations may be set to any suitable time periods.

[0046] Table 2. Exemplary peak magnitude levels and filtering durations

[0048] For the purpose of illustration, the set of peak levels and filtering durations shown in Table 3 may be applied to the waveform in FIG. 8. FIG. 8 shows a waveform 802 subject to filtering according to one embodiment of the present invention. As depicted, the detected peaks A, B and E, are of magnitude of two or three. Thus, according to Table 3, the filtering durations for the peaks A, B and E are zero, i.e., there is no filtering applied after the detection of the peaks A, B, and E. However, since the peak C is of magnitude seven, the non-zero value in DLYMAG7 applies so that any peak detected in the next six samples is ignored and not time-stamped. Stated differently, any peak detected during the time interval 804 is ignored. This is why the sample D is ignored, even though it is a valid peak in the sample stream.

[0049] Timeout mechanism: It is possible that a constant waveform, such as the waveform pattern described in conjunction with FIG. 7, may be processed for the peak detection. In embodiments, when the length of the constant "sample-train" is above a certain threshold (say 256 samples), the leading edge sample of the constant waveform may be set as a "peak". Since the peak is declared on magnitude being constant for 256 samples, DLYMAGx filtering in Table 2, which has a maximum filter length of 255 samples from the peak, does not apply to the timeout peak.

[0050] FIG. 9 shows a constant waveform 902 that is not subject to filtering according to one embodiment of the present invention. As depicted, the sample A is detected as a candidate peak, but the determination that it be a peak depends on a sample of lesser magnitude to arrive sometime later (without a sample of higher magnitude to interject in between the sample A and the sample of lesser magnitude). However, if the constant waveform continues for more than 256 samples, the sample A is declared as a peak. The peak detector continues to process samples without filtration and the next peak is detected in the sample B. Note that the timeout mechanism may have an option to be enabled or disabled.

[0051] Minimum detection magnitude: It is desirable to have the ability to rule out certain samples from being considered as peaks, based on their magnitude. In embodiments, a peak detection mechanism may include a reference 5bit configuration register field which will contain the minimum magnitude for the detection of a peak. A setting of "0" for this configuration register field may be equivalent to disabling this feature.

[0052] It shall be noted that the present invention may be implemented in any instruction-execution/computing device or system capable of processing data, including, without limitation phones, laptop computers, desktop computers, and servers. The present invention may also be implemented into other computing devices and systems. Furthermore, aspects of the present invention may be implemented in a wide variety of ways including software (including firmware), hardware, or combinations thereof. For example, the functions to practice various aspects of the present invention may be performed by components that are implemented in a wide variety of ways including discrete logic components, one or more application specific integrated circuits (ASICs), and/or program- controlled processors. It shall be noted that the manner in which these items are implemented is not critical to the present invention.

[0053] Having described the details of the invention, an exemplary system 1000, which may be used to implement one or more aspects of the present invention, will now be described with reference to FIG. 10. As illustrated in FIG. 10, system 1000 includes a central processing unit (CPU) 1001 that provides computing resources and controls the computer. CPU 1001 may be implemented with a microprocessor or the like, and may also include a graphics processor and/or a floating point coprocessor for mathematical computations. System 1000 may also include a system memory 1002, which may be in the form of random- access memory (RAM) and read-only memory (ROM).

[0054] A number of controllers and peripheral devices may also be provided, as shown in FIG. 10. An input controller 1003 represents an interface to various input device(s) 1004, such as a keyboard, mouse, or stylus. There may also be a scanner controller 1005, which communicates with a scanner 1006. System 1000 may also include a storage controller 1007 for interfacing with one or more storage devices 1008 each of which includes a storage medium such as magnetic tape or disk, or an optical medium that might be used to record programs of instructions for operating systems, utilities and applications which may include embodiments of programs that implement various aspects of the present invention. Storage device(s) 1008 may also be used to store processed data or data to be processed in accordance with the invention. System 1000 may also include a display controller 1009 for providing an interface to a display device 1011, which may be a cathode ray tube (CRT), a thin film transistor (TFT) display, or other type of display. System 1000 may also include a printer controller 1012 for communicating with a printer 1013. A communications controller 1014 may interface with one or more communication devices 1015, which enables system 1000 to connect to remote devices through any of a variety of networks including the Internet, a local area network (LAN), a wide area network (WAN), or through any suitable electromagnetic carrier signals including infrared signals.

[0055] In the illustrated system, all major system components may connect to a bus 1016, which may represent more than one physical bus. However, various system components may or may not be in physical proximity to one another. For example, input data and/or output data may be remotely transmitted from one physical location to another. In addition, programs that implement various aspects of this invention may be accessed from a remote location (e.g., a server) over a network. Such data and/or programs may be conveyed through any of a variety of machine-readable medium including, but are not limited to: magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD-ROMs and holographic devices; magneto-optical media; and hardware devices that are specially configured to store or to store and execute program code, such as application specific integrated circuits (ASICs), programmable logic devices (PLDs), flash memory devices, and ROM and RAM devices.

[0056] Embodiments of the present invention may be encoded upon one or more non- transitory computer-readable media with instructions for one or more processors or processing units to cause steps to be performed. It shall be noted that the one or more non- transitory computer-readable media shall include volatile and non-volatile memory. It shall be noted that alternative implementations are possible, including a hardware implementation or a software/hardware implementation. Hardware-implemented functions may be realized using ASIC(s), programmable arrays, digital signal processing circuitry, or the like. Accordingly, the "means" terms in any claims are intended to cover both software and hardware implementations. Similarly, the term "computer-readable medium or media" as used herein includes software and/or hardware having a program of instructions embodied thereon, or a combination thereof. With these implementation alternatives in mind, it is to be understood that the figures and accompanying description provide the functional information one skilled in the art would require to write program code (i.e., software) and/or to fabricate circuits (i.e., hardware) to perform the processing required.

[0057] It shall be noted that embodiments of the present invention may further relate to computer products with a non-transitory, tangible computer-readable medium that have computer code thereon for performing various computer-implemented operations. The media and computer code may be those specially designed and constructed for the purposes of the present invention, or they may be of the kind known or available to those having skill in the relevant arts. Examples of tangible computer-readable media include, but are not limited to: magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD-ROMs and holographic devices; magneto-optical media; and hardware devices that are specially configured to store or to store and execute program code, such as application specific integrated circuits (ASICs), programmable logic devices (PLDs), flash memory devices, and ROM and RAM devices. Examples of computer code include machine code, such as produced by a compiler, and files containing higher level code that are executed by a computer using an interpreter. Embodiments of the present invention may be implemented in whole or in part as machine-executable instructions that may be in program modules that are executed by a processing device. Examples of program modules include libraries, programs, routines, objects, components, and data structures. In distributed computing environments, program modules may be physically located in settings that are local, remote, or both.

[0058] One skilled in the art will recognize no computing system or programming language is critical to the practice of the present invention. One skilled in the art will also recognize that a number of the elements described above may be physically and/or functionally separated into sub-modules or combined together.

[0059] FIG. 11 shows a schematic diagram of an exemplary system 1100 for transmitting and receiving UWB signals according to one embodiment of the present invention. As depicted, one or more UWB transmitters 1106a - 1106c may transmit UWB signals 1120 to one or more receivers 1104a - 1104n. The output signals from the receivers 1104a - 1104n may be sent to a switching module 1108, such as power-over-Ethernet switch, where the switching module 1108 may control the data flow from the receivers 1104a - 1104n to a server 1110, such as computer. For instance, the switching module 1108 may be coupled to the server 1110 via a single cable for transmitting data from and providing electrical power to the receivers 1104a - 1104n. [0060] It should be noted that any suitable number of UWB transmitters may be included in the system 1100. Likewise, it should be noted that any suitable number of UWB receivers may be included in the system 1100. In embodiments, each of the transmitters 1106a - 1106c may be a tag that is able to transmit UWB signals at a preset frequency. In embodiments, using the UWB signals received by the receivers 1104a - 1104n and the triangulation technique, the exact locations of the transmitters 1106a - 1106c may be determined.

[0061] In embodiments, the receivers 1104a - 1104n may have the capability to perform the peak detections described in conjunction with FIGS. 1A - 8. Also, each receiver may include the system 1100. In other embodiments, the server 1110 may have the capability to perform the peak detections described in conjunction with FIGS. 1A - 8. In such embodiments, the server 1110 may include the system 1100.

[0062] It will be appreciated to those skilled in the art that the preceding examples and embodiment are exemplary and not limiting to the scope of the present invention. It is intended that all permutations, enhancements, equivalents, combinations, and improvements thereto that are apparent to those skilled in the art upon a reading of the specification and a study of the drawings are included within the true spirit and scope of the present invention.