Method and system for decimating an indexed set of data elements

• US 7,755,641 B2
• Filed: 08/13/2002
• Issued: 07/13/2010
• Est. Priority Date: 08/13/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Tseng, Steven, Tsang, Chris
• Primary Examiner(s): Amini; Javid A
• Application Number:
  US10/217,973
• Publication Number:
  US 20040034641A1
• Time in Patent Office: 2,891 Days
• Field of Search: 345/240, 345/204, 345/601, 345/602, 345/581, 345/555, 382/298, 382/166
• US Class Current: 345/601
• CPC Class Codes: H03H 17/0607 comprising a ROM addressed by the input data signals
• CPC Class Codes: H03H 17/0664 where the output-delivery frequency is lower than the input sampling frequency, i.e. decimation

Abstract

A method and system are disclosed for decimating an indexed set of data elements to generate a decimated set of data elements. The indexed set of data elements are grouped into groups of at least two data elements per group. The indexes of the data elements in each group are used to address a look-up-table (LUT) that is pre-programmed to perform the decimation operation. For each group of data elements presented to address the LUT, a decimated data value is output from the LUT. The decimated data value is a function of the data values of the corresponding data elements addressing the LUT.

Claims

1. A method to decimate video pixels in a video processing system, said method comprising:

arranging an indexed set of data elements into groups of at least two data elements;

addressing a pre-programmed look-up-table (LUT) using at least two index values corresponding to said at least two data elements in each of said groups; and

outputting a decimated data value from said LUT in response to each of said groups to generate a decimated set of data elements wherein said decimated data value comprises a filtered data value corresponding to said LUT being pre-programmed to filter data values of said at least two data elements.

2. The method of claim 1 further comprising pre-programming said LUT to output said decimated data value when addressed by said at least two index values.

3. The method of claim 1 wherein said indexed set of data elements is decimated by an integer factor to generate said decimated set of data elements.

4. The method of claim 1 wherein said indexed set of data elements is decimated by a non-integer factor to generate said decimated set of data elements.

5. The method of claim 1 wherein said decimated data value comprises an average data value corresponding to said LUT being pre-programmed to average data values of said at least two data elements.

6. The method of claim 1 wherein said decimated data value comprises at least two components, and wherein each of said at least two components is a function of corresponding components of data values of said at least two data elements.

7. The method of claim 1 wherein each data element of said at least two data elements comprises a data value in a YUVA format.

8. The method of claim 1 wherein said decimated data value is in a YUVA format.

9. The method of claim 1 wherein each index value of said at least two index values comprises 4 bits.

10. The method of claim 1 wherein said decimated data value comprises 32 bits.

11. The method of claim 1 wherein each data value of each of said at least two data elements comprises 32 bits.

12. The method of claim 1 wherein said decimated data value changes when at least one of said at least two index values changes.

13. The method of claim 1 wherein said indexed set of data elements is decimated along a horizontal dimension of said indexed set of data elements to generate said decimated set of data elements.

14. The method of claim 1 wherein said indexed set of data elements is decimated along a vertical dimension of said indexed set of data elements to generate said decimated set of data elements.

15. The method of claim 1 wherein said LUT comprises a programmable memory device.

16. The method of claim 1 wherein said LUT stores at least 256 decimated data values.

17. The method of claim 1 wherein said indexed set of data elements comprise video pixel data.

18. A method for decimating video pixels in a video processing system, said method comprising:

grouping a number of data elements into a plurality of groups, wherein each of said data elements comprises a data value, said data value associated with a corresponding index value of one or more index values, said grouping based on a decimation factor;

addressing a programmable memory using two or more of said index values to access a decimated value; and

outputting said decimated value from said programmable memory, said decimated value computed using a decimation algorithm for computing an average data value of said data elements in each group of said plurality of groups, said decimation algorithm resident in a host processor.

19. The method of claim 18 wherein said index values are generated from a memory module and transmitted to said programmable memory using a first-in-first-out (FIFO) buffer.

20. The method of claim 18 wherein said number comprises 2.

21. The method of claim 18 wherein each of said index values comprises 4 bits.

22. The method of claim 18 wherein said data value comprises 32 bits.

23. The method of claim 18 wherein said decimation factor comprises an integer value.

24. The method of claim 23 wherein said integer value comprises 2.

25. The method of claim 23 wherein said decimation factor comprises a non-integer value.

26. The method of claim 25 wherein said non-integer value comprises 1.5.

27. The method of claim 18 wherein said data value comprises four 8 bit words configured in a YUVA video format.

28. The method of claim 18 wherein said data elements comprise video pixels from a horizontal dimension of a frame.

29. The method of claim 28 wherein said data elements comprise video pixels from a vertical dimension of a frame.

30. A system to decimate an indexed set of data elements, said system comprising:

a memory module storing one or more data values and one or more corresponding index values of said indexed set of data elements;

a programmable memory storing one or more decimated data values;

at least one FIFO used to transmit pairs of said one or more corresponding index values from said memory module, each of said pairs used to address a decimated data value of said one or more decimated data values from said programmable memory; and

a host processor containing a decimation algorithm wherein said decimation algorithm computes an average of data values associated with each pair of said pairs of said one or more corresponding index values.

31. The system of claim 30 wherein said programmable memory comprises an EEPROM.

32. A system to decimate an indexed set of data elements, said system comprising:

a memory module storing said indexed set of data elements;

a programmable memory device storing a decimation look-up-table (LUT);

at least one FIFO to pipeline at least two sets of index values from said memory module to address lines of said programmable memory device; and

a host processor to download said decimation LUT to said programmable memory device, wherein output values of said programmable memory device comprise filtered data values corresponding to said decimation LUT being pre-programmed to filter data values corresponding to said at least two sets of index values.

33. The system of claim 32 wherein said host processor includes a decimation algorithm used to generate said decimation LUT from a pre-defined set of indexed data values.

34. The system of claim 32 wherein said indexed set of data elements comprises video pixel data and corresponding index values.

35. The system of claim 32 wherein said at least two sets of index values correspond to groups of at least two data elements of said indexed set of data elements.

36. The system of claim 32 wherein said programmable memory device outputs a decimated data value when addressed by at least two index values from said at least two sets of index values.

37. The system of claim 32 wherein said indexed set of data elements is decimated by an integer factor to generate a decimated set of data elements.

38. The system of claim 32 wherein said indexed set of data elements is decimated by a non-integer factor to generate a decimated set of data elements.

39. The system of claim 32 wherein each index value of said at least two sets of index values comprises 4 bits.

40. The system of claim 32 wherein said programmable memory device outputs a 32-bit decimation value in a YUVA format when addressed by at least two index values from said at least two sets of index values.

41. The system of claim 32 wherein each data value corresponding to each data element of said indexed set of data elements comprises a 32-bit word in a YUVA format.

42. The system of claim 32 wherein said programmable memory device outputs a 32-bit decimation value that is a function of the data values corresponding to at least two index values from said at least two sets of index values.

43. The system of claim 32 wherein said indexed set of data elements is decimated along a horizontal dimension of said indexed set of data elements to generate a decimated set of data elements.

44. The system of claim 32 wherein said indexed set of data elements is decimated along a vertical dimension of said indexed set of data elements to generate a decimated set of data elements.

45. The system of claim 32 wherein said programmable memory device stores at least 256 32-bit decimation values.

46. The system of claim 32 wherein output values of said programmable memory device comprise averaged data values corresponding to said decimation LUT being pre-programmed to average data values corresponding to said at least two sets of index values.

47. A system to decimate an indexed set of data elements, said system comprising:

a memory module storing said indexed set of data elements;

a programmable memory device storing a decimation look-up-table (LUT);

at least one FIFO to pipeline at least two sets of index values from said memory module to address lines of said programmable memory device; and

a host processor to download said decimation LUT to said programmable memory device, wherein output values of said programmable memory device comprise averaged data values corresponding to said decimation LUT being pre-programmed to average data values corresponding to said at least two sets of index values.

48. The system of claim 47 wherein said host processor includes a decimation algorithm used to generate said decimation LUT from a pre-defined set of indexed data values.

49. The system of claim 47 wherein said indexed set of data elements comprises video pixel data and corresponding index values.

50. The system of claim 47 wherein said at least two sets of index values correspond to groups of at least two data elements of said indexed set of data elements.

51. The system of claim 47 wherein said programmable memory device outputs a decimated data value when addressed by at least two index values from said at least two sets of index values.

52. The system of claim 47 wherein said indexed set of data elements is decimated by an integer factor to generate a decimated set of data elements.

53. The system of claim 47 wherein said indexed set of data elements is decimated by a non-integer factor to generate a decimated set of data elements.

54. The system of claim 47 wherein each index value of said at least two sets of index values comprises 4 bits.

55. The system of claim 47 wherein said programmable memory device outputs a 32-bit decimation value in a YUVA format when addressed by at least two index values from said at least two sets of index values.

56. The system of claim 47 wherein each data value corresponding to each data element of said indexed set of data elements comprises a 32-bit word in a YUVA format.

57. The system of claim 47 wherein said programmable memory device outputs a 32-bit decimation value that is a function of the data values corresponding to at least two index values from said at least two sets of index values.

58. The system of claim 47 wherein said indexed set of data elements is decimated along a horizontal dimension of said indexed set of data elements to generate a decimated set of data elements.

59. The system of claim 47 wherein said indexed set of data elements is decimated along a vertical dimension of said indexed set of data elements to generate a decimated set of data elements.

60. The system of claim 47 wherein said programmable memory device stores at least 256 32-bit decimation values.

61. The system of claim 47 wherein output values of said programmable memory device comprise filtered data values corresponding to said decimation LUT being pre-programmed to filter data values corresponding to said at least two sets of index values.

62. A method comprising:

using an indexed set of data elements stored in a memory module;

storing a decimation look-up-table (LUT) in a programmable memory device;

using at least one FIFO to pipeline at least two sets of index values from said memory module to address lines of said programmable memory device; and

downloading said decimation LUT to said programmable memory device using a host processor, wherein output values of said programmable memory device comprise filtered data values corresponding to said decimation LUT being pre-programmed to filter data values corresponding to said at least two sets of index values.

63. The method of claim 62 wherein said host processor includes a decimation algorithm used to generate said decimation LUT from a pre-defined set of indexed data values.

64. The method of claim 62 wherein said indexed set of data elements comprises video pixel data and corresponding index values.

65. The method of claim 62 wherein said at least two sets of index values correspond to groups of at least two data elements of said indexed set of data elements.

66. The method of claim 62 wherein said programmable memory device outputs a decimated data value when addressed by at least two index values from said at least two sets of index values.

67. The method of claim 62 wherein said indexed set of data elements is decimated by an integer factor to generate a decimated set of data elements.

68. The method of claim 62 wherein said indexed set of data elements is decimated by a non-integer factor to generate a decimated set of data elements.

69. The method of claim 62 wherein each index value of said at least two sets of index values comprises 4 bits.

70. The method of claim 62 wherein said programmable memory device outputs a 32-bit decimation value in a YUVA format when addressed by at least two index values from said at least two sets of index values.

71. The method of claim 62 wherein each data value corresponding to each data element of said indexed set of data elements comprises a 32-bit word in a YUVA format.

72. The method of claim 62 wherein said programmable memory device outputs a 32-bit decimation value that is a function of the data values corresponding to at least two index values from said at least two sets of index values.

73. The method of claim 62 wherein said indexed set of data elements is decimated along a horizontal dimension of said indexed set of data elements to generate a decimated set of data elements.

74. The method of claim 62 wherein said indexed set of data elements is decimated along a vertical dimension of said indexed set of data elements to generate a decimated set of data elements.

75. The method of claim 62 wherein said programmable memory device stores at least 256 32-bit decimation values.

76. The method of claim 62 wherein output values of said programmable memory device comprise averaged data values corresponding to said decimation LUT being pre-programmed to average data values corresponding to said at least two sets of index values.

77. A method comprising:

using an indexed set of data elements stored in a memory module;

storing a decimation look-up-table (LUT) in a programmable memory device;

using at least one FIFO to pipeline at least two sets of index values from said memory module to address lines of said programmable memory device; and

downloading said decimation LUT to said programmable memory device using a host processor, wherein output values of said programmable memory device comprise averaged data values corresponding to said decimation LUT being pre-programmed to average data values corresponding to said at least two sets of index values.

78. The method of claim 77 wherein said host processor includes a decimation algorithm used to generate said decimation LUT from a pre-defined set of indexed data values.

79. The method of claim 77 wherein said indexed set of data elements comprises video pixel data and corresponding index values.

80. The method of claim 77 wherein said at least two sets of index values correspond to groups of at least two data elements of said indexed set of data elements.

81. The method of claim 77 wherein said programmable memory device outputs a decimated data value when addressed by at least two index values from said at least two sets of index values.

82. The method of claim 77 wherein said indexed set of data elements is decimated by an integer factor to generate a decimated set of data elements.

83. The method of claim 77 wherein said indexed set of data elements is decimated by a non-integer factor to generate a decimated set of data elements.

84. The method of claim 77 wherein each index value of said at least two sets of index values comprises 4 bits.

85. The method of claim 77 wherein said programmable memory device outputs a 32-bit decimation value in a YUVA format when addressed by at least two index values from said at least two sets of index values.

86. The method of claim 77 wherein each data value corresponding to each data element of said indexed set of data elements comprises a 32-bit word in a YUVA format.

87. The method of claim 77 wherein said programmable memory device outputs a 32-bit decimation value that is a function of the data values corresponding to at least two index values from said at least two sets of index values.

88. The method of claim 77 wherein said indexed set of data elements is decimated along a horizontal dimension of said indexed set of data elements to generate a decimated set of data elements.

89. The method of claim 77 wherein said indexed set of data elements is decimated along a vertical dimension of said indexed set of data elements to generate a decimated set of data elements.

90. The method of claim 77 wherein said programmable memory device stores at least 256 32-bit decimation values.

91. The method of claim 77 wherein output values of said programmable memory device comprise filtered data values corresponding to said decimation LUT being pre-programmed to filter data values corresponding to said at least two sets of index values.

92. A method to decimate video pixels in a video processing system, said method comprising:

arranging an indexed set of data elements into groups of at least two data elements;

addressing a pre-programmed look-up-table (LUT) using at least two index values corresponding to said at least two data elements in each of said groups; and

outputting a decimated data value from said LUT in response to each of said groups to generate a decimated set of data elements wherein said decimated data value comprises an average data value corresponding to said LUT being pre-programmed to average data values of said at least two data elements.

93. The method of claim 92 further comprising pre-programming said LUT to output said decimated data value when addressed by said at least two index values.

94. The method of claim 92 wherein said indexed set of data elements is decimated by an integer factor to generate said decimated set of data elements.

95. The method of claim 92 wherein said indexed set of data elements is decimated by a non-integer factor to generate said decimated set of data elements.

96. The method of claim 92 wherein said decimated data value comprises a filtered data value corresponding to said LUT being pre-programmed to filter data values of said at least two data elements.

97. The method of claim 92 wherein said decimated data value comprises at least two components, and wherein each of said at least two components is a function of corresponding components of data values of said at least two data elements.

98. The method of claim 92 wherein each data element of said at least two data elements comprises a data value in a YUVA format.

99. The method of claim 92 wherein said decimated data value is in a YUVA format.

100. The method of claim 92 wherein each index value of said at least two index values comprises 4 bits.

101. The method of claim 92 wherein said decimated data value comprises 32 bits.

102. The method of claim 92 wherein each data value of each of said at least two data elements comprises 32 bits.

103. The method of claim 92 wherein said decimated data value changes when at least one of said at least two index values changes.

104. The method of claim 92 wherein said indexed set of data elements is decimated along a horizontal dimension of said indexed set of data elements to generate said decimated set of data elements.

105. The method of claim 92 wherein said indexed set of data elements is decimated along a vertical dimension of said indexed set of data elements to generate said decimated set of data elements.

106. The method of claim 92 wherein said LUT comprises a programmable memory device.

107. The method of claim 92 wherein said LUT stores at least 256 decimated data values.

108. The method of claim 92 wherein said indexed set of data elements comprise video pixel data.