HK1019524A - Method and apparatus for generating a transform - Google Patents

Description

Method and apparatus for generating a transform

Technical Field

The present invention relates to the field of generating transforms such as cyclic redundancy codes, polynomial codes, and hash codes, and more particularly to methods and apparatus for generating transforms.

Background

An example of a prior art transform generation apparatus 10 is shown in fig. 1. The prior art transform generation apparatus 10 has a data register (shift register) 12 and an intermediate remainder register 14. The particular generating means of fig. 1 is designed for calculating a cyclic redundancy code (CRC-16). A plurality of exclusive or circuits 18 are strategically coupled with a plurality of registers 16 in intermediate remainder register 14. The data bits are shifted out of the data register 12 and into the intermediate register 14. When the data bits have been completely shifted into the intermediate register 14, the intermediate register contains a CRC relating to the data bits. The transform generation means may also be encoded in software. Software emulation of hardware to generate transformations has proven to be not an efficient method, so software solutions typically use look-up tables to compute one byte or nibble (four bits) at a time. The lookup table created may be used for any size amount of data (e.g., 1 bit, 10 bits, etc.).

The packetizer (packetizer) calculates the CRC of the newly formed packet using the transform generator. The packetizing means receives packets (data) from respective sources. The received packets are then grouped according to their final destination. If two small packets have the same destination, they are combined into one packet and then transmitted to the destination. In prior art applications, the packetizing means removes the CRC from the two packets and then recalculates the CRC based on the combined data of the two packets. In other cases, the packetizing device may receive one large packet, requiring the packet to be split into two smaller packets. In prior art applications, the CRC of a large packet is discarded and a new CRC is calculated from the scratchpad (scratch) of two smaller packets. This process is not efficient because the CRC of the received packet contains information useful for calculating the CRC of the output packet.

The transform generation means is also for the associative memory. The transform generation means computes a hash code or polynomial code (see USPN 4,527,239 branch) to determine the address of the packet. When a data packet is a combination of two original packets, the prior art associative memory calculates a new translation (address) of the new data packet from the scratchpad. These processing advantages can be realized by the transform generation means that computes the new transform using the old transform.

Thus, there is a need for a transform generation apparatus that generates a new transform from an existing transform without using underlying data.

Disclosure of Invention

A method that overcomes these problems by receiving a first transform associated with a first data string to generate a transform. A second transformation associated with the second data string is also received. The second transform is appended to the first transform to form a first-second combined transform for the first-second data string.

The apparatus for carrying out the method includes an input/output port coupled to a controller. The controller is also coupled to the query memory, the shift module, and the combiner.

Brief description of the drawings

FIG. 1 is a schematic diagram of a prior art transform generation apparatus;

FIG. 2 is a block diagram of a transform generation apparatus according to the present invention;

FIG. 3 is a diagrammatic representation of a shift module used in the transform generation apparatus of FIG. 2;

FIG. 4 is a diagrammatic representation of a combiner used in the transform generation apparatus of FIG. 2;

FIG. 5 is a block diagram of another embodiment of a transform generation apparatus according to the present invention;

FIG. 6 is a flow diagram of a shift module;

FIG. 7 is a flow chart of a not shifting module;

FIG. 8 is a flow diagram of a transformation module;

FIG. 9 is a flow diagram of a do not transform module;

FIG. 10 is a block diagram of an associative memory;

FIG. 11 is a block diagram of a packetizing apparatus;

FIG. 12 is a schematic diagram of a general purpose computer and a computer readable storage medium containing computer readable instructions;

FIG. 13 is a look-up table for a CRC-32 polynomial code; and

fig. 14 is a reverse look-up table for a CRC-32 polynomial code.

Preferred embodiments of the invention

Fig. 2 shows a block diagram of the inventive transform generation apparatus 20. Unlike prior art transform generation devices, transform generation device 20 may calculate a new transform from two previous transforms without reference to the base data. To understand how the transform generation apparatus 20 works, it is helpful to understand some of the underlying mathematics. The underlying mathematics are based on polynomial codes and also include cyclic redundancy codes, but are not limited thereto. These codes can be represented by the following formulas:

X^n-kM(X)=Q(X)G(X)+R(X)

where X is^n-kIs a shift item

M (X) is a message polynomial;

g (X) is a generator polynomial;

q (X) is the quotient obtained when the message is divided by the generator polynomial; and

r (X) is the remainder of the division process.

The remainder is the CRC or transformation of the message. As can be seen from the above formula, the transformation of two messages that have been xored is equal to the xored transformation associated with the two messages. If the first message is "A" and the second message is "B", the combined message is "AB". The message polynomial is:

AB(X)=X^ZA(X)+B(X)

where Z is equal to the number of bits in message B.

And

R_AB(X)=R(X^ZA(X))+R_B(X)

thus, to generate the transformation of the message "AB", we need only combine the transformation of "B" with the transformation of "A0", where 0 denotes Z zeros. When the transformation of "A" and "B" is known, we only need to compute the shifted transformation value of "A" and combine it with the transformation of "B". Fortunately, computing the shift transform is a simple process.

The transformation generating means 20 calculates a new transformation from the existing transformation using the mathematical formula described above. The input/output port 22 is used to receive existing transforms and to output new transforms. The I/O ports 22 are coupled to a controller 24 that coordinates the functions of a memory 26, a shift module 28, and a combiner 30. The memory contains a look-up table for the transformation. An example of such a look-up table is shown in fig. 13. The table in fig. 13 calculates the transform on a byte by byte basis based on the CRC-32 transform. Other tables may be generated for other polynomials. The present invention is not limited to CRC polynomials and may be applied to various other polynomials. The particular polynomial depends on the application of the transform generation means. The function performed by the shift module 28 is to determine a shift transformation. The combiner is arranged to combine (XOR) for example a shifted first transform and a second transform to form the first-second transform. The first-second transformation is defined as a transformation related to the first-second data string (e.g., in the communication example, the second data string is transmitted immediately after the first data string: first-second data string). The process of shifting the first transform and combining it with the second transform is called appending. The transformation generating means can be implemented in software or using hardware consisting of a memory, a microprocessor and some shift registers and xor gates.

Fig. 3 shows a schematic diagram of a shift module 28 used by the transformation generating device 20. The transform to be shifted is stored in a transform register 40 having an input 42, a shift control 44 and an output 46. Output 46 is coupled to an exclusive or gate 48. The query register 50 contains entries that are selected using pointers derived from the transform to be shifted. The look-up register 50 has an input 52, a shift control 54 and an output 56. Output 56 is coupled to a second input of exclusive or gate 48. The output 58 of the exclusive or gate is stored in an output register 60. After appropriate processing, output register 60 contains a shift transition, which is transmitted to controller 24 via output 62.

Fig. 4 shows a schematic diagram of a combiner 30 used by the transform generation apparatus 20. The outputs of the first register 70 and the second register 72 are coupled to an exclusive or gate 74. In one example, the first register 70 contains a shifted first transition and the second register 72 contains a second transition. The output of the xor gate 74 is coupled to an output register 76. Once the shifted first transition is combined with the second transition, the output register 76 contains the first-second transition.

Fig. 5 is a block diagram of another embodiment of the transform generation apparatus 100 according to the present invention. The transform generation apparatus 100 has an I/O port 22 coupled to a controller 24. The controller 24 communicates with the memory 26, the shift module 28, the no shift module 104, the transform module 106, the no transform module 108, and the combiner 30 over the bus 102. Memory 26 contains a look-up table (e.g., the table in fig. 13) and an inverse look-up table (an example of which is shown in fig. 14). The reverse look-up table described in fig. 14 is based on the same CRC-32, which uses a byte-by-byte approach. Transform generation device 100 of fig. 5 may combine transforms similar to transform generation device 20 of fig. 2. Further, the transform generation apparatus 100 may determine a first-second transform that gives the first transform and the second data string or gives the first data string and the second transform. The transform generation device 100 may remove the second transform from the first-second combined transform to determine the first transform. In practice, the transform generation apparatus 100 allows a complete transform process to be performed on a transform that gives enough input as a transform or data. After describing each module in detail with reference to fig. 6-9, how this is achieved will be described in more detail.

FIG. 6 is a flow chart of the shift module. The shift module determines the shift message (i.e., "A0" -X^ZA (X)) is performed. Processing begins at step 120 with receiving a transform 122 to be shifted at step 124. Next, the pointer 126 is extracted at step 128. Then, at step 130, transform 122 is shifted to the right by the number of bits of pointer 126. This forms the shift pointer 132. Note that the words left and right are used for convenience, and they are based on the convention that the most significant bit is usually located on the left. When a different convention is used, the word left and right must be changed to accommodate the convention. Next, at step 136, the shift transform 132 is combined with the entry 134 for the associated pointer 126. This forms a shift transformation 138 at step 140, ending the process at step 142. Note that if the reason for shifting the first transform is to generate the first-second transform, the first transform must be shifted by the number of bits of the second data string. This is done by executing the shift module X times, where X equals the number of data bits in the second data string divided by the number of bits in the pointer. Note that another way to implement the shift module is to use a polynomial generation device similar to that shown in fig. 1. The first transformation 122 is placed in the intermediate redundancy register 14. Then, some logical zeros (nulls) are processed, the number of which is equal to the number of data bits in the second data string.

FIG. 7 is a flow chart of a not shifting module. One example of when to use the module is when the transformation of the data string "AB" is combined with the transformation of the data string "B". This leaves a data string "A0" or X^ZTransformation of A (X). This transformation must be "unshifted" to find the transformation for data string "a". Processing begins at step 150 with the receipt of a shift transform 152 at step 154. At step 156, a back pointer 158 is extracted. The backpointer 158 is equal to the highest portion 160 of the shift transform 152. At step 164, the reverse pointer 158 is combined with the pointer 162 in the reverse lookup table (see, e.g., FIG. 14). The entry 166 associated with the pointer 162 is then combined with the shift transform. This produces an intermediate product 170 at step 172. At step 174, intermediate product 170 is shifted to the left to form a shiftBit intermediate 176. The shifted intermediate product 176 is then combined with the pointer 162 to form the transformation 180 at step 178, ending the process at step 182. Note that if the number of bits in the "B" data string is not equal to the number of bits in the pointer, the no shift module is executed X times, where X = z/(number of bits in the pointer).

FIG. 8 is a flow chart of a transformation module. The transformation module may determine a first-second transformation for the first-second data string given the first transformation and the second data string without first converting the second data string to the second transformation. Processing commences at 190 whereupon the lowest portion 192 of the first transformation 194 is extracted at 194. This portion is combined with the second data string 196 to form a pointer 198 at step 200. Next, at step 206, the shifted first transformation 202 is combined with the entry 204 for the pointer in the relevant look-up table (e.g., FIG. 12). At step 210, the combined transform 208 is generated, ending the process at step 212. Note that if the pointer is one byte long, the transform module can only process one byte of data at a time. When the second data string is longer than one byte, the transformation module executes one byte of data at a time until the entire second data string has been executed. In another example, assuming that the first transform is equal to all zeros (null), the combined transform is only a transform for the second data string. In another embodiment, the first transformation may be a prerequisite and the obtained transformation is a prerequisite-second transformation. In another example, assume that a four-level transformation is desired for a four-level data string. The first data portion (e.g., byte) in the four-level data string is extracted. It points to an entry in the look-up table. When the fourth data string does not contain only the first data portion, the next data portion is extracted. The next data portion is combined with the lowest part of the item to form a pointer. The term is then shifted to the right by the number of bits in the next data portion to form a shifted term. The shift entry is combined with a second entry related to the pointer. This process is repeated until the entire four-level data string has been processed.

FIG. 9 is a flow chart of a do not transform module. The non-transform module may determine a first transform for the first data string that gives the first-second transform and the second data string. Processing begins at step 220 and the highest portion 222 of the first-second transform 224 is extracted at step 226. The highest portion 222 is a reverse pointer associated with pointer 228 in the reverse lookup table. The pointer is accessed at step 230. Next, at step 236, the first-second transformation 224 is combined with the item 232 associated with the pointer to form an intermediate product 234. At step 238, the intermediate product is shifted to the left by the number of bits in pointer 228. This forms a shifted intermediate product 240. Next, the pointer 228 is combined with the second data string 242 to form the result 244 at step 246. At step 250, the result 244 is combined with the shifted intermediate product 240 to form a first transformation 248, and the process ends at step 252. If the second data string is longer than the pointer, the module repeats a number of times.

Some examples of the transformation module 100 may include determining a second-third transformation from the first-second-third transformation and the first transformation. The first transformation shifts the number of data bits in the second-third data strings. The shifted first transform is combined with the first-second-third transform to form a second-third transform. In another example, the transform generator 100 may determine the first-second-third-fourth transform after receiving the fourth data string. In one example, the transform module may first calculate a fourth transform (using the transform module). The first-second-third transforms are shifted by the number of bits in the fourth data string using a shift module. The shifted first-second-third transform is then combined with a fourth transform using a combiner.

Fig. 10 is a block diagram of associative memory 300. Associative memory 300 uses translation generator 302 to associate a data string with an address and a confirmer. Typically, the address is one half of the translation, and the confirmer is equal to the other half of the translation. Directory 304 stores a list of addresses and their associated confirmers and links as necessary. A linked list is necessary to resolve any conflicts. If two different data strings are mapped to the same address, a conflict is created. The linked list points to another address where the conflicting data string is stored. The confirmer is used to identify whether the correct address associated with the data string has been accessed. The directory shows the addresses where the data strings are stored in the memory (memory) 306. This process is controlled by a controller 308 which communicates with the outside world through an input/output port 310. If all the data strings have a fixed length, the directory entry 304 may not be used. The use of the transformation generator 302 allows easy querying if the first transformation and the second transformation are known to store the first-second data string. A fast search may also be performed for the reverse order (i.e., second-first data string). Various other fast search paths will also be apparent to those skilled in the art. Note that the requirements for the subject polynomial of the associative memory are different from the requirements for the polynomial of the CRC. As a result, many other polynomial generators may be used in this application.

Fig. 11 is a block diagram of a packetizing apparatus 320. The packetizer 320 is another example of an apparatus using the transform generator 322 described herein. In one example, the packet device is part of a router. The controller 326 receives incoming packets 324. The controller 326 forms outgoing packets 328 from the incoming packets 324. Typically, outgoing packets 328 have a fixed length and incoming packets 324 have an indeterminate length or different lengths. Typically, no incoming data has yet formed a packet. An outgoing packet 334 may be formed from two small packets 330, 332 destined for the same destination. The data packet includes a data portion ("a" or "B") and a CRC or transform [ r (a) or r (B) ]. Given the CRC of each packet 330, 332, the CRC [ R (AB) of the combined packet ("AB") 334 can be quickly determined using the transform generator 322. In another example, the incoming packet 336 is too large and must be split into two packets 338, 340. Two new CRCs can be easily computed by first computing the transformation (e.g., [ r (c) ] of the shorter of the two data strings and removing the transformation from the combined transformation to form the other CRC [ r (d)) ]. Another example that may be envisaged is the need for more additional processing of the required CRC. The transform generator described herein can perform all of these calculations without having to use a register of the underlying data to recalculate the CRC.

FIG. 12 is a schematic diagram of a general-purpose computer 350 and a computer-readable storage medium 352 containing computer-readable instructions. The computer-readable storage medium 352 contains instructions that are executed by the computer 350 to perform the functions of the transform generator 100. These instructions may be separate or part of a set of instructions that perform the functions of the associative memory 300 or the functions of the packet means 320.

Thus, a transform generator has been described that can determine a combined transform from a plurality of independent transforms without having to access the following data. In addition, the transform generator may perform various other transform processes that are generated in the packetizing means and the associative memory. The use of the transform generator is not limited to the two examples described herein (i.e., associative memory and packetizing means). Many other applications will be apparent to those skilled in the art.

While the invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art in light of the foregoing description. Accordingly, it is intended to embrace those alternatives, modifications, and variations that fall within the spirit and scope of the appended claims.

Claims (20)

1. A method of generating a transform, comprising the steps of:

(a) receiving a first transformation associated with a first data string;

(b) receiving a second transformation associated with a second data string; and

(c) the second transform is appended to the first transform to produce a first-second combined transform for the first-second data string.

2. The method of claim 1, further comprising the steps of:

(d) removing the second transform from the first-second combined transform to form a shifted first transform;

(e) the shifted first transform is not shifted to form a first transform.

3. The method of claim 2, wherein the step of not shifting comprises the steps of:

extracting a backpointer from the shifted first transform;

(ii) reading a pointer in the reverse lookup table;

(iii) combining a member of the look-up table associated with the pointer with the shifted first transformation to form an intermediate product;

(iv) left shifting the intermediate by the number of bits in the pointer to form a shifted intermediate; and

(v) combining the moved intermediate with the pointer.

4. A method as claimed in claim 3, wherein steps (i) to (v) are repeated X times, where X is equal to the number of bits in the pointer divided by the number of bits in the second data string.

5. The method of claim 1, wherein the additional step comprises the steps of:

shifting the first transform to the right by the number of bits in the second data string to form a shifted first transform; and

(ii) combining the shifted first transform with the second transform.

6. The method of claim 1 wherein the transformation is the result of applying a polynomial code to the data string.

7. The method of claim 6 wherein the polynomial code is a cyclic redundancy code.

8. The method of claim 1, further comprising the steps of:

(d) a first-second-third transformation associated with the first-second-third data string is received.

(e) The first transform shifts the number of bits in the second-third data strings to form a shifted first transform; and

(f) the first-second-third transform is combined with the shifted first transform to form a second-third transform.

9. The method of claim 8, further comprising the steps of:

(g) receiving a fourth data string;

(h) calculating a fourth transformation;

shifting the number of bits in the fourth data string by the first-second-third transforms to form shifted first-second-third transforms; and

(j) the shifted first-second-third transform is combined with the fourth transform to form a first-second-third-fourth transform.

10. The method of claim 9 wherein the step of computing a fourth transformation further comprises the steps of:

extracting a first data portion of a fourth data string;

(ii) accessing a member of the look-up memory table associated with the first data portion;

(iii) when the fourth data string does not contain only the first data, extracting a next data portion;

(iv) combining the next data portion with the lowest portion of the member to form a pointer;

(v) moving the member to the right by the number of bits in the next data portion to form a moved member;

(vi) combining the moved member with a second member associated with the pointer; and

(vii) repeating steps (iv) through (vi) until all fourth data strings have been processed.

11. The method of claim 8, wherein the step of shifting comprises the steps of:

extracting a pointer from the first transform;

(ii) the first transformation shifts the number of bits in the pointer to the right to form a shifted first transformation;

(iii) combining the first transformation of the move with a member of a lookup table associated with the pointer.

12. The method of claim 11, wherein steps (i) through (iii) are repeated X times, where X is equal to the number of bits in the pointer divided by the number of bits in the second-third data string.

13. The method of claim 8, wherein the step of shifting comprises the steps of:

placing a first transform in an intermediate register of a polynomial generator;

(ii) a number of logical zeros equal to the number of bits in the second-third data string are processed.

14. A computer readable storage medium containing computer readable instructions which, when inserted into a computer, perform the steps of:

(a) receiving a first transformation associated with a first data string;

(b) receiving a second transformation associated with a second data string; and

(c) the second transform is appended to the first transform to produce a first-second combined transform for the first-second data string.

15. The computer-readable storage medium of claim 14, further comprising the steps of:

(d) removing the second transform from the first-second combined transform to form a shifted first transform;

(e) the shifted first transform is not shifted to form a first transform.

16. The computer-readable storage medium of claim 14, wherein the additional step comprises the steps of:

shifting the first transform to the right by the number of bits in the second data string to form a shifted first transform; and

(ii) combining the shifted first transform with the second transform.

17. A transform generator, comprising:

an input/output port;

a controller coupled to the input/output port;

a query memory coupled to the controller;

a shift module coupled to the controller; and

a combiner coupled to the controller.

18. The transform generator of claim 17 further comprising a no-shift module coupled to the controller.

19. The transform generator of claim 17 further comprising a transform module coupled to the controller.

20. The transform generator of claim 17, further comprising an un-transform module coupled to the controller.