Data reordering using buffers and memory

Patent metadata

Field	Value
Publication number	US-10061537-B2
Application number	US-201514826031-A
Country	US
Kind code	B2
Filing date	Aug 13, 2015
Priority date	Aug 13, 2015
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

Apparatus and methods are disclosed for reordering data received in a non-contiguous order into a contiguous order. In one example of the disclosed technology, an apparatus includes a number of input buffers comprising at least a first, first-in first-out (FIFO) input buffer and a second FIFO input buffer, a number of FIFO output buffers, and a reorder unit configured to store a first portion of non-contiguous data received from an image sensor in the first input buffer, store a second portion of the received data in the second FIFO input buffer, store a respective pixel of data output by the first and second FIFO input buffers at a first address location in the memory, and traverse the memory according to an order to store the respective pixels in a FIFO output buffer. The apparatus can thus be used to reorder pixel data prior to further image processing.

First claim

We claim:

1. An apparatus configured to reorder data received from a data stream into a contiguous ordering, the data being arranged according to a first ordering, the apparatus comprising:
a plurality of input buffers comprising a first input buffer and a second input buffer, each of the input buffers being configured to output data stored by the respective input buffer in a first-in first-out order;
an addressable memory;
a plurality of output buffers, each of the output buffers being configured to output data stored by the respective output buffer in a respective first-in first-out order; and
control circuitry configured to cause the apparatus to:
store a first portion of the received data in the first input buffer, the first portion comprising a first plurality of data units,
store a second portion of the received data in the second input buffer, the second portion comprising a second plurality of data units,
store a first data unit of a first portion output by the first input buffer and a second data unit of a second portion output by the second input buffer at a first address location in the addressable memory, and
store the first data unit and the second data unit output from the memory in a first one of the output buffers, thereby producing reordered data.

2. The apparatus of claim 1 , wherein the control circuitry is further configured to cause the apparatus to:
store a third data unit of the first portion and a fourth data unit of the second portion at a second address location in the memory; and
store the third data unit and the fourth data unit in a second one of the output buffers.

3. The apparatus of claim 1 , wherein each of the buffers are FIFO buffers implemented using circuitry including at least one or more of the following: a series of chained latches, a series of chained flip-flops, or a static random access memory (SRAM).

4. The apparatus of claim 1 , wherein each of the buffers are implemented as at least one or more of the following: shift registers or FIFO buffers, and wherein each of the buffers are a synchronous FIFO buffer or an asynchronous FIFO buffer.

5. The apparatus of claim 1 , further comprising an image sensor, wherein the image sensor is configured to generate the received data as a series of pixels in a non-contiguous order, and wherein each of the data units corresponds to a pixel of the series of pixels.

6. An apparatus configured to reorder data received from a data stream into a contiguous ordering, the data being arranged according to a first ordering, the apparatus comprising:
a plurality of input buffers comprising a first input buffer and a second input buffer, each of the input buffers being configured to output data stored by the respective input buffer in a first-in first-out order;
an addressable memory;
control circuitry configured to cause the apparatus to:
store a first portion of the received data in the first input buffer, the first portion comprising a first plurality of data units,
store a second portion of the received data in the second input buffer, the second portion comprising a second plurality of data units,
store a first data unit of a first portion output by the first input buffer and a second data unit of a second portion output by the second input buffer at a first address location in the addressable memory, wherein the control circuitry is operable to be reconfigured to reorder data received in a second ordering different than the first ordering into a contiguous ordering.

7. The apparatus of claim 6 , further comprising:
a plurality of output buffers, each of the output buffers being configured to output data stored by the respective output buffer in a respective first-in first-out order; and
wherein the control circuitry is further configured to cause the apparatus to:
store the first data unit and the second data unit output from the memory in a first one of the output buffers, thereby producing reordered data.

8. The apparatus of claim 6 , wherein the control circuitry is further configured to cause the apparatus to:
store a third data unit of the first portion and a fourth data unit of the second portion at a second address location in the memory; and
store the third data unit and the fourth data unit in a second one of the output buffers.

9. The apparatus of claim 6 , wherein each of the buffers are FIFO buffers implemented using circuitry including at least one or more of the following: a series of chained latches, a series of chained flip-flops, or a static random access memory (SRAM).

10. The apparatus of claim 6 , wherein each of the buffers are implemented as at least one or more of the following: shift registers or FIFO buffers, and wherein each of the buffers are a synchronous FIFO buffer or an asynchronous FIFO buffer.

11. The apparatus of claim 6 , further comprising an image sensor, wherein the image sensor is configured to generate the received data as a series of pixels in a non-contiguous order, and wherein each of the data units corresponds to a pixel of the series of pixels.

12. An apparatus configured to reorder non-contiguous pixel data into a contiguous ordering, the apparatus comprising:
an addressable memory;
a plurality of first-in first-out (FIFO) input buffers; and
logic configured to cause the apparatus to reorder the non-contiguous pixel data into a contiguous pixel stream by:
storing respective portions of the pixel data in each of the FIFO input buffers and selecting a respective pixel concurrently output by each of the FIFO input buffers, and
storing a set of the selected pixels as a word in the addressable memory.

13. The apparatus of claim 12 , further comprising:
a plurality of FIFO output buffers, wherein the word of pixels stored in the memory are output using the plurality of FIFO output buffers.

14. The apparatus of claim 12 , wherein the non-contiguous pixel data is ordered according to a complex sequence based on an odd number of terms, the terms of the sequence being incremented by an even number.

15. The apparatus of claim 12 , wherein the logic comprises reorder unit means for reordering the received pixel data into the contiguous pixel stream.

16. The apparatus of claim 12 , wherein the logic is further configured to cause the apparatus to:
store a first set of pixels in a first one of the FIFO input buffers;
store a second set of pixels in a second one of the FIFO input buffers; and
store a first respective pixel output by each of the FIFO input buffers at a first address location of an addressable memory.

17. The apparatus of claim 12 , further comprising a sensor coupled to the FIFO input buffers, the sensor being configured to produce the non-contiguous pixel data.

18. A method of reordering a stream of pixel data having a non-contiguous ordering into a contiguous ordering, the method comprising:
storing a first set of pixels from the stream in a first input FIFO;
storing a second set of pixels from the stream in a second input FIFO;
storing a first pixel of the first set of pixels output by the first input FIFO and a second pixel of the second set of pixels output by the second input FIFO in a memory at a first address location;
copying the first pixel and the second pixel to an output FIFO buffer from the memory; and
outputting the first pixel and the second pixel from the output FIFO buffer according to a contiguous ordering.

19. The method of claim 18 , further comprising generating the stream of pixel data using an image sensor, the image sensor being configured

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kersh Michael
• Haraden Ryan

Classifications

• G06F3/0656 Primary

  Data buffering arrangements · CPC title

• G06F5/065 Primary

  Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's · CPC title

• G06F13/4013

  with data re-ordering, e.g. Endian conversion · CPC title

• G06F3/0683

  Plurality of storage devices · CPC title

• H04N19/423

  characterised by memory arrangements (H04N19/433 takes precedence) · CPC title