Method and apparatus for interleaving data streams

In one embodiment, an optimized interleaving instruction is provided. The interleaving instruction facilitates a bit-level interleaving of two streams of data stored in two source registers into a combined stream of data.

BACKGROUND OF THE INVENTION

Open Systems Interconnection (OSI) is a standard description or “reference model” for how messages should be transmitted between any two points in a telecommunication network. The purpose of OSI is to guide product implementors so that their products will consistently work with other products. The reference model defines seven layers of functions that take place at each end of communication. The first layer (also referred to as the physical layer) conveys the bit stream through the network at the electrical and mechanical levels. The physical layer provides the hardware means of sending and receiving data on a carrier. The physical layer is defined by various specifications. For instance, the IEEE 802.11a standard defines the physical layer for wireless LAN communications, Bluetooth™ defines the physical layer for communications involving mobile phones, computers, and personal digital assistants, etc.

A number of current physical layer algorithms involves bit manipulation of data streams. For instance, the “Convolutional Encoder” algorithm used in the IEEE 802.11a standard generates two streams of encoded bits which are then interleaved into a single stream of data using the “Interleaver” algorithm. Naive software implementation of the “Interleaver” algorithm would result in an inefficient and time-consuming code. Thus, a mechanism for optimizing existing physical layer algorithms is needed.

DESCRIPTION OF EMBODIMENTS

A method and apparatus for interleaving two streams of data are described. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention can be practiced without these specific details.

FIG. 1is a block diagram of one embodiment of a processing system. Processing system100includes processor120and memory130. Processor120can be any type of processor capable of executing software, such as a microprocessor, digital signal processor, microcontroller, or the like. Processing system100can be a personal computer (PC), mainframe, handheld device, portable computer, set-top box, or any other system that includes software.

Memory130can be a hard disk, a floppy disk, random access memory (RAM), read only memory (ROM), flash memory, or any other type of machine medium readable by processor120. Memory130can hold data and also store instructions for performing the execution of the various method embodiments of the present invention such as a method300described below in conjunction withFIGS. 3.

Referring now toFIG. 2, a more detailed block diagram of an exemplary processor120in which the present invention may be implemented is illustrated. It should be noted that a variety of processors other than processor120can be used to implement the present invention without loss of generality.

Processor120includes an instruction cache21to store instructions received from memory130and a data cache22to store computer data received from memory130. There is also provided a data RAM23which is accessible to software for efficiency and an interrupt controller24which provides a means for requesting interrupts.

Processor120communicates with external components such as memory130through an external bus32. The bus control unit25is used to direct data transfer into and out of the processor. According toFIG. 2, processor120includes three functional units for carrying out instructions. However, processor120may contain more or less than three functional units. The functional units illustrated onFIG. 2include a multiply divide unit27, an execution/address generation unit28and a memory interface unit38for processing memory requests based on addresses generated by execution/address generation unit28. Instructions are propagated to the functional units through an instruction sequencer26which is coupled to instruction cache21via an instruction bus42. Instruction sequencer26receives instructions from instruction cache21and decodes instructions to be executed by one of the functional units. Typically, an instruction code (for register instruction) will include an operation code and provide information identifying the location of the source operands for the instruction (SRC1and/or SRC2) as well as indicating a destination (DEST) address for the result of the operation by the execution units.

Within the processor illustrated inFIG. 2, all operations take place at the register level. Source operands specify a global register, a local register or a constant value as instruction operands. The functional units are coupled to the register file30via bus48.

In one embodiment, register file30includes two source registers which may hold two streams of data. The two streams of data may be transferred to processor120from an external source (e.g., memory130) or may be created as a result of one or more internal operations. In one embodiment, instruction cache21stores an interleaving instruction (referred to as bit_interleaver) received from memory130. Instruction sequencer26decodes the bit_interleaver instruction and transfers it to execution/address generation unit28. Execution/address generation unit executes the bit_interleaver instruction, thereby interleaving two streams of data from the source registers into one stream of data in a destination register. The bit_interleaver instruction performs the interleaving operation at a bit-level as opposed to prior art interleaving operations that are performed for bytes, words or double-words (e.g., Intel multimedia (MMX™) instructions such as punpcklbw, punpcklwd, and punpckldq). Performing the interleaving operation at a bit level reduces the code size and the number of executed instructions involved in the interleaving. The bit_interleaver instruction will be described in greater detail below.

FIG. 3is a flow diagram of a method300for interleaving two streams of data, according to one embodiment of the present invention. Method300begins with receiving an interleaving instruction (referred to as “bit_interleaver”) at processing block304. At processing block306, two streams of data are identified. In one embodiment, the bit_interleaver instruction specifies locations of two source registers storing the above streams of data. In one embodiment, each of the two streams of data is a stream of encoded data bits created by the “Convolutional Encoder” algorithm which will be described in greater detail below. Alternatively, the data streams may be created by any known in the art communication or general algorithm other than the “Convolutional Encoder” algorithm if such an algorithm includes bit manipulation (e.g., Bluetooth™ physical layer algorithms or other IEEE 802.11a algorithms). Each of the two streams of data includes 16 data bits. It should be noted that the length of the data streams may vary (e.g., the data streams may include 8 bits, 32 bits, 64 bits, etc.) and therefore should not limit the scope of the present invention.

At processing block308, a bit-level interleaving operation is performed on the two streams of data, generating a combined stream of data. The bit-level interleaving operation is performed by executing the bit_interleaver instruction. In one embodiment, the execution of the bit_interleaver instruction results in moving data bits of the first stream to even positions of a destination register and moving data bits of the second stream to odd positions of the destination register, thereby creating a combined stream of data in the destination register. The bit_interleaver instruction is described in greater detail below in conjunction withFIG. 6.

FIG. 4illustrates an exemplary “Convolutional Encoder” algorithm404in which the bit_interleaver instruction may be implemented. The “Convolutional Encoder” algorithm404described herein is defined by the IEEE 802.11a standard.

The algorithm404receives a stream402of data bits and generates two streams of encoded bits: stream406and stream408. The streams of encoded bits are generated using any known in the art technique (e.g., the industry-standard generator polynomials g0=1138and g1=1718, of rate R=½). The encoded streams are then interleaved by an interleaver algorithm410, generating one stream412of data bits. Conventional interleaver algorithms include multiple instructions to facilitate interleaving of data bits of the two streams. For instance, a reduced instruction set computing (RISC) microprocessor design implements an interleaver algorithm illustrated inFIG. 5.

Referring toFIG. 5, a prior art method500for interleaving two streams of data is shown. The two streams of data bits are stored in registers R1and R2. Registers R3and R4are used as temporary registers, register R5stores the loop counter and register R6stores the resulting stream of interleaved bits.

Method500begins with placing the value of 1 in the 0-bit position of register R3(processing block504). Next, the value representing the number of iterations is placed into register R5(processing block506), and the data stream stored in register R2is shifted one position to the left (processing block508). Further, processing blocks510-526are performed to interleave bit0of the first data stream and bit0of the second data stream. At processing block526, the number of iterations is reduced by one, and a determination is made as to whether the number of iterations reached the value of zero (decision box528). If the number of iterations is not equal to zero, processing blocks510-526are repeated until all bits of the two streams are interleaved (i.e., until R5=0).

Accordingly, the code size of the interleaver algorithm illustrated onFIG. 5is equal to 13 instructions, and the executed number of instructions is equal to 163 (i.e., the first 3 instructions and the loop resulting in 10 instructions executed 16 times). The bit_interleaver instruction reduces both the code size of the above algorithm and the number of executed instructions, thereby providing an efficient mechanism for performing bit-level interleaving operations.

The bit_interleaver instruction operates on two source registers and performs bit interleaving on their lower 16 bits into a destination register. The syntax of the bit_interleaver instruction can be written as follows:
Dest=Bit_Interleaver(Src1, Src2)  (1)
The semantics of the bit_interleaver instruction can be expressed as

Dest⁡(i)={Src1⁡(i2)⁢⁢For⁢⁢i=0,2,4,6,…⁢,30Src2⁡(i-12)⁢⁢For⁢⁢i=1,3,5,7,…⁢,31(2)
where Dest(i) represents positions of bits in the destination register,

Src2⁡(i2)
represents positions of bits in the first source register, and

Src2⁡(i-12)
represents positions of bits in the second source register.

FIG. 6illustrates the execution of a bit-interleaver instruction, according to one embodiment of the present invention. Register602is a first source register, register604is a second source register, and register606is a destination register. Using the above formula 2, the processor places data bits of the first stream into even positions of the destination register and data bits of the second stream into odd positions of the destination register. Accordingly, the code size of the prior art interleaver algorithm is reduced from 13 to 1 and the number of executed instruction is reduced from 163 to 1.