System for determining median values of video data

• US 8,751,990 B2
• Filed: 12/19/2008
• Issued: 06/10/2014
• Est. Priority Date: 12/19/2008
• Status: Expired due to Fees

• Current Assignee: L-3 Communications Corporation (L3Harris Technologies, Inc.)
• Original Assignee: L-3 Communications Integrated Systems LP (L3Harris Technologies, Inc.)
• Inventors: Standfield, Matthew R., Allen, Jim D., Flores, Juan Esteban, Fox, Michael O'Neal, Prasanna, Deepak, DeLaquil, Matthew P.
• Primary Examiner(s): SYED, FARHAN M
• Application Number:
  US12/340,166
• Publication Number:
  US 20100161695A1
• Time in Patent Office: 1,999 Days
• US Class Current: 716/116
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc

Abstract

A system for determining the median of a plurality of data values comprises a plurality of field programmable gate arrays (FPGA), a plurality of inter FPGA links, an input router, a plurality of median modules, and a plurality of output transfer modules. Each FPGA includes a plurality of configurable logic elements and configurable storage elements from which the other components are formed. The inter FPGA link allows communication from one FPGA to another. The input router receives the plurality of data values and creates a plurality of data streams. The median module receives at least one data stream, increments a plurality of counters corresponding to a single data value within the range of data values, and determines the median by accumulating the contents of each counter. The output transfer module transfers the median to an external destination along with performance statistics of the determination of the median.

Claims

1. A system for determining the median of a plurality of data values, the system comprising:

a processor and a memory element communicatively coupled thereto, the memory element configured to store a plurality of instructions to be executed by the processor for determining the median of a plurality of data values;

a plurality of field programmable gate arrays (FPGA) including a plurality of configurable logic elements and a plurality of configurable storage elements;

an input router formed from the configurable logic elements and configured to receive the data values and create a plurality of data streams, each data stream including a portion of the data values; and

a plurality of median modules formed from the configurable logic elements and the configurable storage elements and configured to receive at least one data stream, each median module including

a plurality of counters, each counter with an address corresponding to a single data value within the range of data values and each counter being incremented when the corresponding data value is received,

an accumulator configured to accumulate the contents of each counter in sequential order,

a comparator configured to compare the contents of the accumulator with the total number of the data values divided by two, wherein the comparator generates a signal if the contents of the accumulator is greater than or equal to the total number of the data values divided by two, and

an address register coupled to the comparator, the address register configured to track the address of the counters as the contents of each counter are accumulated and to determine the median upon receipt of the signal from the comparator.

2. The system of claim 1, further including a plurality of inter FPGA links, each inter FPGA link included within one FPGA and configured to allow communication from one FPGA to another FPGA.

3. The system of claim 1, further including a plurality of output transfer modules, each output transfer module included within one FPGA and configured to transfer the median to an external destination along with performance statistics of the determination of the median.

4. The system of claim 1, wherein the plurality of counters includes at least one dual-port memory element coupled to an adder, wherein the adder is configured to add one to the contents of each address of the at least one dual-port memory element.

5. The system of claim 4, wherein each dual-port memory element includes an address to correspond to each data value in the range of data values.

6. The system of claim 4, wherein the accumulator is coupled to a data bus of the at least one dual-port memory element and configured to accumulate the contents of each address of the at least one dual-port memory element in sequential order.

7. The system of claim 6, wherein the contents of each address of the at least one dual-port memory element are reset to zero at the same time as the contents of each address are accumulated.

8. The system of claim 4, wherein each median module further includes an address generator coupled to an address bus of the at least one dual-port memory elements and configured to generate each address of the at least one dual-port memory element in sequential order.

9. A system for determining the median of a plurality of data values, the system comprising:

a processor and a memory element communicatively coupled thereto, the memory element configured to store a plurality of instructions to be executed by the processor for determining the median of a plurality of data values;

a plurality of field programmable gate arrays (FPGA) including a plurality of configurable logic elements and a plurality of configurable storage elements;

a plurality of inter FPGA links, each inter FPGA link included within one FPGA and configured to allow communication from one FPGA to another FPGA;

an input router formed from the configurable logic elements and is configured to receive the data values and create a plurality of data streams, each data stream including a portion of the data values;

a plurality of median modules formed from the configurable logic elements and the configurable storage elements and configured to receive at least one data stream, each median module including

a plurality of counters, each counter corresponding to a single data value within the range of data values and each counter being incremented when the corresponding data value is received,

an accumulator configured to accumulate the contents of each counter in sequential order,

a comparator configured to compare the contents of the accumulator with the total number of the data values divided by two, wherein the comparator generates a signal if the contents of the accumulator is greater than or equal to the total number of the data values divided by two, and

an address register coupled to the comparator, the address register configured to track the address of the counters as the contents of each counter are accumulated and to determine the median upon receipt of the signal from the comparator; and

a plurality of output transfer modules, each output transfer module included within one FPGA and configured to transfer the median to an external destination along with performance statistics of the determination of the median.

10. The system of claim 9, wherein the plurality of counters includes at least one dual-port memory element coupled to an adder, wherein the adder is configured to add one to the contents of each address of the at least one dual-port memory element.

11. The system of claim 10, wherein the at least one dual-port memory element includes an address to correspond to each data value in the range of data values.

12. The system of claim 10, wherein the accumulator is coupled to a data bus of the at least one dual-port memory element and configured to accumulate the contents of each address of the at least one dual-port memory element in sequential order.

13. The system of claim 10, wherein each median module further includes an address generator coupled to an address bus of the at least one dual-port memory elements and configured to generate each address of the at least one dual-port memory element in sequential order.

14. A system for determining the median of a plurality of data values, the system comprising:

a processor and a memory element communicatively coupled thereto, the memory element configured to store a plurality of instructions to be executed by the processor for determining the median of a plurality of data values;

a plurality of field programmable gate arrays (FPGA) including a plurality of configurable logic elements and a plurality of configurable storage elements;

a plurality of inter FPGA links, each inter FPGA link included within one FPGA and configured to allow communication from one FPGA to another FPGA;

an input router formed from the configurable logic elements and is configured to receive the data values and create a plurality of data streams, each data stream including a portion of the data values;

a plurality of median modules formed from the configurable logic elements and the configurable storage elements and configured to receive at least one data stream, and further including

at least one dual-port memory element coupled to an adder, wherein the adder is configured to add one to the contents of each address of the at least one dual-port memory element,

an address generator coupled to an address bus of the at least one dual-port memory element and configured to generate each address of the at least one dual-port memory element in sequential order,

an accumulator coupled to a data bus of the at least one dual-port memory element and configured to accumulate the contents of each address of the at least one dual-port memory element in sequential order,

a comparator configured to compare the contents of the accumulator with the total number of the data values divided by two and to generate a signal if the contents of the accumulator is greater than or equal to the total number of the plurality of data values divided by two, and

an address register coupled to the comparator, the address register configured to track the address of the counters as the contents of each counter are accumulated and to determine the median upon receipt of the signal from the comparator; and

a plurality of output transfer modules, each output transfer module included within one FPGA and configured to transfer the median to an external destination along with performance statistics of the determination of the median.

15. A computer implemented method for determining the median of a plurality of data values, the method comprising the steps of:

a) establishing a processor and a memory element communicatively coupled thereto, the memory element configured to store a plurality of instructions to be executed by the processor for determining the median of a plurality of data values;

b) establishing at least one dual-port memory element within a field programmable gate array (FPGA) wherein the at least one dual-port memory element includes an address that corresponds to each value in the range of data values;

c) receiving all of the data values into the FPGA;

d) counting the occurrence of each data value in the data values by incrementing the contents of the address that corresponds to the data value;

e) sequentially accumulating the contents of each address of the at least one dual-port memory element utilizing an accumulator within the FPGA;

f) comparing the contents of the accumulator after each address is accumulated with the total number of the data values divided by two after each address is accumulated utilizing a comparator within the FPGA; and

g) generating the median as being the current address of the at least one dual-port memory element when the contents of the accumulator equals the total number of the data values divided by two.

16. The method of claim 15, further including the step of splitting the plurality of data values into a plurality of data streams within the FPGA to be received by the at least one dual-port memory element.

17. The method of claim 15, further including the step of resetting the contents of each address of the at least one dual-port memory element to zero at the same time as the contents of each address is accumulated.

18. The method of claim 15, wherein incrementing the contents of the address that corresponds to the data value of step c) utilizes an adder coupled with the dual-port memory element.