JP4973042B2 - Data position conversion apparatus and data position conversion method - Google Patents

Description

  The present invention relates to a data position conversion apparatus and a data position conversion method for converting a data storage position, and more particularly to a data position conversion apparatus and a data position conversion method for converting a storage position of data stored in a memory.

  Currently, digital signal processing is performed in various fields such as wireless communication and image analysis. In digital signal processing, data analysis processing using fast Fourier transform (FFT), inverse fast Fourier transform (IFFT), or the like is frequently performed. Here, in FFT or the like, it is known that the order of input data does not match the order of output data corresponding to the input data.

  Specifically, the order of input data and the order of output data corresponding to the input data are in a bit-inversion relationship. Bit inversion is to reverse a binary bit string (see, for example, Patent Document 1). For example, in the case of a data string in which the data position can be expressed by 3 bits, that is, in the case of a data string composed of eight data from position 0 (000) to position 7 (111), position 1 (001) Corresponds to the output data at position 4 (100). Thus, when input data is given in the order of 0, 1, 2, 3, 4, 5, 6, 7, the corresponding output data is output in the order of 0, 4, 2, 6, 1, 5, 3, 7. Is done.

Therefore, in a digital signal processing apparatus, input data is rearranged before processing such as FFT so that output data is output in the correct order. Such data rearrangement is generally performed when input data used for processing such as FFT is stored in a memory. That is, when the data output by the preceding process such as FFT is stored in the memory, for example, the data at the position 1 is stored at the address 100 instead of the address 001. As a result, when all the input data is stored in the memory, the input data is arranged in an appropriate order, and processing such as FFT can be started immediately. In addition, this method has an advantage that the apparatus configuration can be simplified.
JP 59-033575

  However, the above method has a problem that it is difficult to use the data stored in the memory for other purposes. For example, there is a case where it is desired to extract statistical information from time series data as necessary before performing FFT. However, since the order is rearranged for FFT processing when the data is stored in the memory, the time series is extracted. The characteristics are lost, making statistical processing difficult. As described above, when the apparatus is configured using the above method, the order of data processing is fixed and lacks flexibility.

  On the other hand, the above problem can be solved by temporarily storing input data in the memory in the original order and rearranging the memory data immediately before performing processing such as FFT. However, conventionally, there has been a problem that the process of rearranging data stored in the memory becomes complicated and the apparatus scale increases. The reason is as follows.

  In order to rearrange the memory data, it is necessary to calculate a set of memory addresses having a bit inversion relationship without excess or deficiency. Here, when the memory addresses are counted up sequentially from the minimum value to the maximum value, and the inversion addresses of the respective memory addresses are obtained in order, the memory addresses to be paired appear twice. For example, when a 3-bit memory address is counted up as 000,001,010,011,100,101,110,111, the corresponding inverted address is 000,100,010,110,001,101,011,111. Is calculated.

  Here, an address group (001, 100) and an address group (100, 001) appear. Since these are the same address group, the memory data replacement process is performed when the address group (001, 100) is found. If it does, replacement processing should not be performed when the address set (100, 001) is found. This is because if the replacement process is performed twice, the data returns to the original position. The above control cannot be realized with a simple device configuration, and it is necessary to prepare a temporary memory area for the rearrangement process. This problem is caused by the fact that it is not easy to obtain a set of memory addresses having a bit inversion relationship without excess or deficiency.

  Note that the above problem occurs not only when data is rearranged for input data before FFT or the like, but also when data is rearranged for output data after FFT or the like. .

  The present invention has been made in view of the above points, and is a data position conversion device for exchanging data stored in a memory between addresses having a bit inversion relationship without increasing the complexity of processing or the scale of the device. It is another object of the present invention to provide a data position conversion method.

  In order to solve the above-described problems, the present invention provides a data position conversion apparatus as shown in FIG. The data position conversion apparatus according to the present invention exchanges data stored in a memory between two memory addresses having a bit inversion relationship. The data position conversion apparatus 1 includes an address generation unit 1a, an address conversion unit 1b, an address adjustment unit 1c, and a data replacement unit 1d. The address generation means 1a continuously generates all the basic addresses that can be expressed with a predetermined bit length by changing the value by one. The address conversion unit 1b generates a first bit string obtained by shifting the basic address by one bit to the right and a second bit string obtained by reversing the first bit string for every two basic addresses that differ only in the least significant bit. When the value of the first bit string is less than or equal to the value of the second bit string, the address adjusting unit 1c determines that the combination of the first bit string and the second bit string is a replacement address, and the value of the first bit string is When the value is larger than the value of the second bit string, a set of bit strings obtained by logically inverting the first bit string and the second bit string is determined as a replacement address. Each time the replacement address is determined, the data replacement unit 1d replaces the storage positions of the two data in the memory 2 specified by the replacement address.

  According to such a data position conversion apparatus 1, the address generation means 1a continuously generates a basic address having a predetermined bit length while changing the value by one. The address conversion unit 1b generates a first bit string obtained by shifting the basic address by one bit to the right and a second bit string obtained by reversing the first bit string for every two basic addresses that differ only in the least significant bit. . Next, when the first bit string is larger than the second bit string, the address adjusting unit 1c determines that a pair obtained by logically inverting the two bit strings is a replacement address. Otherwise, the pair of two bit strings is determined. Is determined as a replacement address. Then, the data replacement means 1d replaces the storage positions of the two data in the memory 2 specified by the replacement address.

  In order to solve the above problem, in the data position conversion method for converting the storage position of the data stored in the memory, the address generation means sets all basic addresses that can be expressed by a predetermined bit length to 1 as the value. The address conversion means generates a first bit string obtained by shifting the basic address by one bit to the right for each of the two basic addresses that differ only in the least significant bit, and the first bit string. A second bit string in reverse order, and the address adjusting means, when the value of the first bit string is less than or equal to the value of the second bit string, the first bit string and the second bit string A set is determined as a replacement address, and when the value of the first bit string is larger than the value of the second bit string, the first bit string and the second bit string are logically inverted. A group of data strings is determined as the replacement address, and each time the replacement address is determined, the data replacement unit replaces the storage positions of the two data in the memory specified by the replacement address. A data position conversion method is provided.

  According to such a data position conversion device, a basic address having a predetermined bit length is continuously generated while changing its value by 1, and the basic address is set to 1 bit for every two basic addresses that differ only in the least significant bit. A first bit string shifted to the right and a second bit string obtained by reversing the first bit string are generated. Next, when the first bit string is larger than the second bit string, a pair obtained by logically inverting the two bit strings is determined as a replacement address. Otherwise, a pair of two bit strings is determined as a replacement address. The Then, the storage positions of the two data in the memory specified by the replacement address are switched.

  The present invention generates a first bit string obtained by shifting the basic address by one bit to the right and a second bit string obtained by reversing the first bit string for each of two basic addresses that differ only in the least significant bit. When the bit string is larger than the second bit string, a pair obtained by logically inverting the two bit strings is determined as a replacement address, and in other cases, a pair of two bit strings is determined as a replacement address. As a result, during the round of the basic address, a set of memory addresses whose data is to be replaced is generated one by one without excess or deficiency. Therefore, it is not necessary to prepare a temporary memory area and the like, and the memory data rearrangement process can be realized with a simple and small-scale device configuration. Further, the memory data rearrangement process can be executed at higher speed.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. First, an outline of the present invention will be described, and then specific contents of the embodiment will be described.
FIG. 1 is a diagram showing an outline of a data position conversion apparatus. The data position conversion apparatus shown in FIG. 1 replaces data stored in a memory between two memory addresses having a bit inversion relationship. The data position conversion apparatus 1 includes an address generation unit 1a, an address conversion unit 1b, an address adjustment unit 1c, and a data replacement unit 1d.

  The address generation means 1a continuously generates all the basic addresses that can be expressed with a predetermined bit length by changing the value by one. For example, the memory counter is counted up from the minimum value (0) to the maximum value (2 ^ N-1: N is the bit length), or counted down from the maximum value (2 ^ N-1) to the minimum value (0). In this way, the basic address is continuously generated. When the memory address can be expressed by 4 bits, 16 addresses from 0000 to 1111 are generated continuously.

  The address conversion unit 1b generates a first bit string obtained by shifting the basic address by one bit to the right and a second bit string obtained by reversing the first bit string for every two basic addresses that differ only in the least significant bit. That is, the address conversion unit 1b generates two bit strings for every two even-numbered and odd-numbered adjacent basic addresses generated by the address generation unit 1a.

  For example, a first bit string 0011 and a second bit string 1100 are generated for two basic addresses 0110 and 0111. Similarly, a first bit string 0100 and a second bit string 0010 are generated for two basic addresses 1000 and 10001. The 1-bit right shift operation is a bit operation that deletes the least significant bit (LSB) of the bit string and inserts 0 into the most significant bit (MSB).

  The address adjusting unit 1c compares the first bit string and the second bit string generated by the address converting unit 1b for each pair. Here, when the value of the first bit string is equal to or less than the value of the second bit string, a set of the first bit string and the second bit string is determined as a replacement address. On the other hand, when the value of the first bit string is larger than the value of the second bit string, a set of bit strings obtained by logically inverting the first bit string and the second bit string is determined as a replacement address.

  That is, in principle, the set of the first bit string and the second bit string generated by the address conversion unit 1b is determined as a set of memory addresses for exchanging data. However, two sets of the same bit string may be generated while the address generation means 1a makes a round of the address counter. Here, the case where the same set of bit strings appears for the second time is limited to the case where the value of the first bit string is larger than the value of the second bit string. At this time, a set of bit addresses obtained by logically inverting the first bit string and the second bit string (inverted 0 and 1 of each bit) is used as a replacement address, whereby a set of memory addresses to which data is to be replaced. Are generated one by one without excess or deficiency.

  For example, the replacement address (0011, 1100) is generated for the set of the first bit string 0011 and the second bit string 1100. On the other hand, replacement addresses (1011 and 1101) are generated for the set of the first bit string 0100 and the second bit string 0010. This is because the set of the first bit string 0010 and the second bit string 0100 has already appeared.

  Each time the replacement address is determined, the data replacement unit 1d replaces the storage positions of the two data in the memory 2 specified by the replacement address. Specifically, the data replacement unit 1d reads data from the memory 2 using two memory addresses, and then writes the read data back to the memory 2 using opposite memory addresses.

  For example, when data D is stored at address 0011 and data M is stored at address 1100, after processing by data replacement means 1d, data M is stored at address 0011 and data D is stored at address 1100. Similarly, when the data L is stored in the address 1011 and the data N is stored in the address 1101, after the processing by the data replacement unit 1d, the data N is stored in the address 1011 and the data L is stored in the address 1101.

  As a result, during the round of the basic address, a set of memory addresses whose data is to be replaced is generated one by one without excess or deficiency. Therefore, it is not necessary to prepare a temporary memory area and the like, and the memory data rearrangement process can be realized with a simple and small-scale device configuration. Further, the memory data rearrangement process can be executed at higher speed.

Embodiments of the present invention will be specifically described below with reference to the drawings. First, a first embodiment of the present invention will be described.
FIG. 2 is a diagram showing a system configuration of the present embodiment. In the wireless communication system of the present embodiment, a base station receives radio waves transmitted from a mobile station, and the base station performs digital signal processing.

  The radio communication system according to the present embodiment includes a base station 100, a receiving antenna 11, and a mobile station 20. The mobile station 20 transmits digital signals on radio waves. The receiving antenna 11 receives radio waves transmitted from the mobile station 20. The base station 100 acquires a digital signal via the receiving antenna 11, and then performs data conversion processing such as FFT. The base station 100 includes a control unit 110, an A / D conversion unit 120, a memory 130, a data position conversion unit 140, and an FFT unit 150. Note that description of processing after the frequency component data is output by FFT is omitted.

  The control unit 110 controls the entire signal processing executed in the base station 100. For example, the control unit 110 transmits a signal indicating processing timing to each component of the base station 100. The A / D converter 120 converts the analog signal acquired from the receiving antenna 11 into a digital signal. Also, filter processing or the like is performed as necessary. Then, the A / D conversion unit 120 stores the time series data in the memory 130.

  The memory 130 holds the data output from the A / D conversion unit 120. The memory 130 is a dual port memory, and by specifying two memory addresses, data at two locations can be read / written simultaneously. The data position conversion unit 140 rearranges the data stored in the memory 130 in accordance with an instruction from the control unit 110. This is because it is necessary to rearrange the input data in advance so that the output data of the FFT unit 150 is in the correct order. The FFT unit 150 sequentially reads the data stored in the memory 130, executes the FFT, and outputs frequency component data. The output data of the FFT unit 150 is used as input data for subsequent processing (not shown).

Next, the module configuration of the data position conversion unit 140 will be described.
FIG. 3 is a block diagram illustrating functions of the data position conversion unit according to the first embodiment. The data position conversion unit 140 includes an address generation unit 141, a bit string operation unit 142, a bit string selection unit 143, an address adjustment unit 144, and a data replacement unit 145. Note that the address generation unit 141 is connected to the control unit 110. The data replacement unit 145 is connected to the memory 130.

  Upon receiving the address generation start signal, the address generation unit 141 continuously generates an N-bit basic address from the minimum value to the maximum value, one unit time (clock). That is, the address generation unit 141 counts up the memory counter from 0 to 2 ^ N-1, and makes a round. For example, when the memory address is 4 bits, 16 addresses from 0000 to 1111 are generated in 16 clocks.

  The bit string operation unit 142 generates an N-bit bit string A, an N-bit bit string B, and a 1-bit flag C for each basic address generated by the address generation unit 141. Next, the bit string selection unit 143 generates an N-bit bit string D and a 1-bit flag E from the bit string A, the bit string B, and the flag C generated by the bit string operation unit 142. Then, the address adjustment unit 144 generates one N-bit memory address from the bit string D and the flag E generated by the bit string selection unit 143.

  In this way, the address adjustment unit 144 generates one memory address every clock. Here, the memory address generated by the address adjustment unit 144 has a meaning as a replacement address for every two consecutive memory addresses. That is, a set of memory addresses having a bit inversion relationship such as 0001 and 1000 is generated every two clocks.

  The data replacement unit 145 replaces the storage position of the data stored in the memory 130 using the replacement address generated by the address adjustment unit 144. Specifically, the data replacement unit 145 reads two memory data from the memory 130 by designating two memory addresses. Then, the data replacement unit 145 writes two memory data by designating memory addresses opposite to each other. The data replacement unit 145 has a register 145a for temporarily storing a memory address or the like.

  Since the memory 130 is a dual port memory, reading / writing of two memory data can be performed in one clock. Therefore, the data replacement unit 145 can replace one set of memory data every two clocks. When the address generation unit 141 makes a round of the address counter, the rearrangement process for all the data stored in the memory 130 is completed.

  In this embodiment, the address conversion process is performed in series for each basic address, and the data replacement process is performed for every two basic addresses. This is to reduce the circuit scale. However, the address conversion process may be performed in parallel for two basic addresses. In this case, the processing of the data position conversion unit 140 can be further accelerated.

Next, a process for calculating a replacement address from a basic address, which is executed by the bit string operation unit 142, the bit string selection unit 143, and the address adjustment unit 144 will be described.
FIG. 4 is a flowchart illustrating a procedure of replacement address determination processing according to the first embodiment. In the following, the process illustrated in FIG. 4 will be described in order of step number.

[Step S11] The bit string operation unit 142 acquires one basic address generated by the address generation unit 141.
[Step S12] The bit string operation unit 142 generates a bit string A obtained by shifting the base address to the right by one bit. Here, the 1-bit right shift operation is to delete the LSB and insert 0 into the MSB.

  [Step S13] The bit string operation unit 142 generates a bit string B corresponding to the bit string A obtained by bit inversion. Specifically, the bit string excluding the LSB of the basic address is inverted to generate a bit string B in which 0 is inserted into the LSB.

[Step S14] The bit string operation unit 142 generates a flag C which is the LSB of the basic address.
[Step S15] The bit string selection unit 143 acquires the bit string A, the bit string B, and the flag C generated by the bit string operation unit 142. Then, the bit string selection unit 143 determines 0/1 of the flag C. If the flag C is 0, the process proceeds to step S16. If the flag C is 1, the process proceeds to step S17.

[Step S16] The bit string selection unit 143 outputs the bit string A acquired in step S15 as a bit string D.
[Step S17] The bit string selection unit 143 outputs the bit string B acquired in step S15 as a bit string D.

  [Step S18] The bit string selection unit 143 compares the bit string A and the bit string B acquired in step S15, and determines the magnitude of the value. If the value of bit string A is greater than the value of bit string B, the process proceeds to step S19. If the value of bit string A is equal to or less than the value of bit string B, the process proceeds to step S20.

[Step S19] The bit string selection unit 143 outputs 1 as the flag E.
[Step S20] The bit string selection unit 143 outputs 0 as the flag E.
[Step S21] The address adjusting unit 144 acquires the bit string D and the flag E generated by the bit string selecting unit 143. Then, the address adjustment unit 144 determines 0/1 of the flag E. If the flag E is 0, the process proceeds to step S22. If the flag E is 1, the process proceeds to Step S23.

[Step S22] The address adjustment unit 144 outputs the bit string D as one of the replacement addresses.
[Step S23] The address adjustment unit 144 outputs a bit string obtained by logically inverting the bit string D as one of the replacement addresses. Here, logical inversion is a bit operation that inverts 0/1 of each bit.

  In this way, the bit string operation unit 142 generates a bit string A obtained by shifting the basic address by one bit to the right, a bit string B obtained by bit-inverting the bit string A, and a flag C that is the LSB of the basic address. The bit string selection unit 143 selects the bit string A as the bit string D when the flag C = 0 (basic address is an even number) and the bit string B when the flag C = 1 (the basic address is odd number). Further, the bit string selection unit 143 outputs 0 as the flag E when bit string A ≦ bit string B, and 1 when bit string A> bit string B. Then, the address adjustment unit 144 uses, as one of the replacement addresses, the bit string D when the flag E is 0 (bit string A ≦ bit string B), and the bit string D when the flag E is 1 (bit string A> bit string B). The logically inverted version of is output.

  FIG. 5 is a diagram illustrating a flow of bit string operations according to the first embodiment. FIG. 5 shows an example in which the memory address is 4 bits. The data position conversion unit 140 advances the bit string operation from the left side to the right side for each row in FIG.

  For example, from the basic address 0110, a bit string A = 0011, a bit string B = 1100, a flag C = 0, a bit string D = 0011, and a flag E = 0 are generated in order. Similarly, from the basic address 0111, the bit string A = 0011, the bit string B = 1100, the flag C = 1, the bit string D = 1100, and the flag E = 0 are generated in order. Here, since the flag E = 0, (0011, 1100) is the replacement address.

  Also, from the basic address 1000, a bit string A = 0100, a bit string B = 0010, a flag C = 0, a bit string D = 0100, and a flag E = 1 are generated in order. Similarly, from the basic address 1001, a bit string A = 0100, a bit string B = 0010, a flag C = 1, a bit string D = 0010, and a flag E = 1 are generated in order. Here, since the flag E = 1, (1011 1101) becomes the replacement address.

  As shown in FIG. 5, when the address length is 4 bits, 8 sets of memory addresses are generated as replacement addresses. Among these, the groups where the values of the two memory addresses are not the same are (0001, 1000), (0010, 0100), (0011, 1100), (1011, 1101), (0101, 1010), (0111, 1110) 6 sets. These six sets are all of the memory address groups whose data is to be replaced. In this way, the data position conversion unit 140 generates replacement addresses without excess or deficiency.

  In the present embodiment, replacement processing is performed even when the values of two memory addresses are the same, such as (0000,0000) and (0110,0110). This is because the circuit scale increases when the comparison operation is performed. However, a comparison operation may be performed after the replacement address is generated, and the replacement process may be performed only when the two memory addresses are different. Thereby, the number of times of reading / writing with respect to the memory 130 can be reduced.

  FIG. 6 is a diagram showing the state of the memory data before and after conversion according to the first embodiment. When the data replacement process is performed according to the flow shown in FIGS. 4 and 5, the state of the memory shown on the left side of FIG. 6 changes to the state shown on the right side. For example, data D at address 0011 and data M at address 1100 are interchanged. Similarly, data L at address 1011 and data N at address 1101 are interchanged.

  By using such a data position conversion device, a set of memory addresses to which data is to be replaced is generated without excess or deficiency during a round of the basic address, and sequential data replacement processing is executed. Therefore, it is not necessary to prepare a temporary memory area or the like, and the memory data rearrangement process can be realized with a simple and small circuit configuration. Further, the memory data rearrangement process can be executed at higher speed.

  Since such a data rearrangement process may be executed immediately before the FFT, the time-series data stored in the memory can be used for other purposes before the FFT, and flexible data processing can be performed. The same advantages as described above can be obtained when the memory data is rearranged after the FFT.

  Next, a second embodiment of the present invention will be described in detail with reference to the drawings. Differences from the first embodiment will be mainly described, and description of similar matters will be omitted. The data position conversion apparatus according to the second embodiment does not perform the data rearrangement process on the entire memory address, but performs the data rearrangement process by dividing the memory address into predetermined intervals. is there.

  FIG. 7 is a block diagram illustrating functions of the data position conversion unit according to the second embodiment. The data position conversion unit 160 corresponds to the data position conversion unit 140 of the first embodiment, and is replaced with the data position conversion unit 140 having the system configuration shown in FIG.

  The data position conversion unit 160 includes an address generation unit 161, a bit string operation unit 162, a bit string selection unit 163, an address adjustment unit 164, a data replacement unit 165, and an offset storage unit 166. Here, the address generation unit 161 and the data replacement unit 165 have the same configuration and function as the address generation unit 141 and the data replacement unit 145 of the first embodiment.

  First, the bit string operation unit 162 outputs the upper M bits of the basic address generated by the address generation unit 161 to the offset storage unit 166. Here, M is a preset integer of 1 or more and less than N (bit length of memory address), and means the bit length of the offset portion. Then, the bit string operation unit 162 generates a bit string A, a bit string B, and a flag C using the bit string from which the upper M bits of the basic address are deleted. Here, the bit string A and the bit string B are NM bits. The offset storage unit 166 holds the M-bit bit string acquired from the bit string operation unit 162.

  The bit string selection unit 163 generates an NM-bit bit string D and a 1-bit flag E from the bit string A, the bit string B, and the flag C generated by the bit string operation unit 162. The address adjustment unit 164 generates an NM-bit bit sequence from the bit sequence D and flag E generated by the bit sequence selection unit 163, and further inserts an M-bit bit sequence held by the offset storage unit 166 in the upper order to obtain N bits One memory address is generated.

Next, processing for calculating a replacement address from a basic address, which is executed by the bit string operation unit 162, the bit string selection unit 163, and the address adjustment unit 164 will be described.
FIG. 8 is a flowchart showing the procedure of the replacement address determination process according to the second embodiment. In the following, the process illustrated in FIG. 8 will be described in order of step number.

[Step S31] The bit string manipulation unit 162 acquires one basic address generated by the address generation unit 161.
[Step S32] The bit string operation unit 162 outputs the upper M bits of the basic address to the offset storage unit 166.

[Step S33] The bit string operation unit 162 generates a bit string A by shifting the bit string excluding the upper M bits of the basic address to the right by one bit.
[Step S34] The bit string operation unit 162 generates a bit string B corresponding to the bit string A obtained by bit-inversion.

[Step S35] The bit string operation unit 162 generates a flag C which is the LSB of the basic address.
[Step S36] The bit string selection unit 163 acquires the bit string A, the bit string B, and the flag C generated by the bit string operation unit 162. Then, the bit string selection unit 163 determines 0/1 of the flag C. If the flag C is 0, the process proceeds to step S37. If the flag C is 1, the process proceeds to step S38.

[Step S37] The bit string selection unit 163 outputs the bit string A acquired in step S36 as a bit string D.
[Step S38] The bit string selection unit 163 outputs the bit string B acquired in step S36 as a bit string D.

  [Step S39] The bit string selection unit 163 compares the bit string A and the bit string B acquired in step S36 to determine the magnitude of the value. If the value of bit string A is greater than the value of bit string B, the process proceeds to step S40. If the value of bit string A is equal to or less than the value of bit string B, the process proceeds to step S41.

[Step S40] The bit string selection unit 163 outputs 1 as the flag E.
[Step S41] The bit string selection unit 163 outputs 0 as the flag E.
[Step S42] The address adjustment unit 164 acquires the bit string D and the flag E generated by the bit string selection unit 163. Then, the address adjusting unit 164 determines 0/1 of the flag E. If the flag E is 0, the process proceeds to step S43. If the flag E is 1, the process proceeds to Step S44.

[Step S43] The address adjustment unit 164 determines that the bit string D is a replacement lower address.
[Step S44] The address adjustment unit 164 replaces the bit string obtained by logically inverting the bit string D with a replacement lower address.

  [Step S45] The address adjustment unit 164 uses, as one of the replacement addresses, an N-bit bit string obtained by adding the bit string output to the offset storage unit 166 in Step S32 above the replacement lower address determined in Step S43 or Step S44. Output.

  In this way, the bit string operation unit 162 generates the bit string A, the bit string B, and the flag C using the bit string obtained by deleting the upper M from the basic address. The bit string selection unit 163 selects the bit string A as the bit string D when the flag C = 0 and the bit string B when the flag C = 1. Further, the bit string selection unit 163 outputs 0 as a flag E when bit string A ≦ bit string B, and 1 when bit string A> bit string B. Then, as one of the replacement addresses, the address adjustment unit 164 logically inverts the bit string D obtained by adding the upper M bits of the basic address to the bit string D when the flag E is 0, and the bit string D when the flag E is 1. A bit string with the upper M bits of the basic address added is output.

  FIG. 9 is a diagram illustrating a flow of bit string operations according to the second embodiment. FIG. 9 shows an example in which the memory address is 5 bits and the upper 1 bit is used as an offset portion.

  As shown in FIG. 9, bit string operations similar to those in the first embodiment are performed on the lower 4 bits of the basic address. On the other hand, the upper 1 bit that is the offset portion is not subject to bit inversion. That is, a replacement address (00001, 01000) is generated from the basic addresses 0010 and 00001. Similarly, replacement addresses (10001, 11000) are generated from the basic addresses 10010 and 10011.

  In this way, by setting the fixed bit length of the offset portion, the memory can be divided into a plurality of areas, and the data can be rearranged within each section. In the example of FIG. 9, data rearrangement is performed in two sections of memory addresses 00000-01111 and 10000-11111.

  FIG. 10 is a diagram illustrating a state of memory data before and after conversion according to the second embodiment. When the data replacement process is performed according to the flow shown in FIGS. 8 and 9, the state of the memory shown on the left side of FIG. 10 changes to the state shown on the right side. For example, the data D1 at address 00001 and the data M1 at address 01100 are interchanged. Similarly, data D2 at address 10011 and data M2 at address 11100 are interchanged.

  By using such a data position conversion device, it is possible to obtain the same effect as when the data position conversion device shown in the first embodiment is used. Furthermore, by using the data position conversion device, the memory address can be divided into a plurality of sections, and data can be rearranged within each section. Therefore, data rearrangement can be flexibly controlled according to the data to be handled and the nature of the data processing to be executed. Further, such control can be easily realized without increasing the circuit scale.

  The data position conversion apparatus and the data position conversion method of the present invention have been described based on the illustrated embodiment. However, the present invention is not limited to this, and the configuration of each unit is an arbitrary function having the same function. It can be replaced with the configuration of Moreover, other arbitrary structures and processes may be added to the present invention.

Further, the present invention may be a combination of any two or more configurations (features) of the above-described embodiments.
The main technical features of the embodiment described above are as follows.

(Supplementary note 1) In a data position conversion device for converting the storage position of data stored in a memory,
Address generation means for continuously generating all the basic addresses that can be expressed by a predetermined bit length by changing the value by 1;
Address conversion means for generating a first bit string obtained by shifting the basic address by one bit to the right and a second bit string obtained by reversing the first bit string for every two basic addresses that differ only in the least significant bit. ,
When the value of the first bit string is equal to or less than the value of the second bit string, a set of the first bit string and the second bit string is determined as a replacement address, and the value of the first bit string is An address adjusting means for determining, as the replacement address, a set of bit strings obtained by logically inverting the first bit string and the second bit string, respectively, when the value is larger than the value of the second bit string;
Data replacement means for replacing the storage positions of two data in the memory specified by the replacement address each time the replacement address is determined;
A data position conversion device comprising:

(Supplementary Note 2) When the fixed bit length indicating the offset portion is designated in advance, the address converting unit uses a bit string that is deleted from the upper bits of the basic address by the fixed bit length instead of the basic address. Generating the first bit string and the second bit string;
The address adjusting means adds the fixed bit length bit string deleted by the address converting means to the higher order of the set of bit strings determined as the replacement address, respectively.
The data position conversion apparatus according to claim 1, wherein:

(Supplementary Note 3) In a data position conversion method for converting a storage position of data stored in a memory,
The address generation means continuously generates all the basic addresses that can be expressed by a predetermined bit length by changing the value by 1.
The address conversion unit generates, for each of the two basic addresses that differ only in the least significant bit, a first bit string obtained by shifting the basic address to the right by one bit and a second bit string obtained by reversing the first bit string. And
When the value of the first bit string is less than or equal to the value of the second bit string, the address adjustment unit determines that the combination of the first bit string and the second bit string is a replacement address, and the first bit string When the value of the bit string is larger than the value of the second bit string, a set of bit strings obtained by logically inverting the first bit string and the second bit string is determined as the replacement address;
Each time the replacement address is determined, the data replacement means replaces the storage positions of the two data in the memory specified by the replacement address.
A data position conversion method characterized by that.

(Supplementary Note 4) In a data position conversion program for converting the storage position of data stored in a memory,
Computer
Address generating means for continuously generating all basic addresses that can be expressed by a predetermined bit length by changing the value by 1;
Address conversion means for generating a first bit string obtained by shifting the basic address by one bit to the right and a second bit string obtained by reversing the first bit string for each of the two basic addresses that differ only in the least significant bit.
When the value of the first bit string is equal to or less than the value of the second bit string, a set of the first bit string and the second bit string is determined as a replacement address, and the value of the first bit string is An address adjusting means for determining, as the replacement address, a set of bit strings obtained by logically inverting the first bit string and the second bit string, respectively, when the value is larger than the value of the second bit string;
Data replacement means for replacing the storage positions of the two data in the memory specified by the replacement address each time the replacement address is determined;
A data position conversion program characterized by functioning as:

It is a figure which shows the outline | summary of a data position conversion apparatus. It is a figure which shows the system configuration | structure of this Embodiment. It is a block diagram which shows the function of the data position conversion part which concerns on 1st Embodiment. It is a flowchart which shows the procedure of the determination process of the replacement address which concerns on 1st Embodiment. It is a figure which shows the flow of the bit stream operation which concerns on 1st Embodiment. It is a figure which shows the state of the memory data before and behind the conversion which concerns on 1st Embodiment. It is a block diagram which shows the function of the data position conversion part which concerns on 2nd Embodiment. It is a flowchart which shows the procedure of the determination process of the replacement address which concerns on 2nd Embodiment. It is a figure which shows the flow of the bit stream operation which concerns on 2nd Embodiment. It is a figure which shows the state of the memory data before and behind the conversion which concerns on 2nd Embodiment.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Data position conversion apparatus 1a Address generation means 1b Address conversion means 1c Address adjustment means 1d Data replacement means 2 Memory

Claims (3)

In a data position conversion device for converting the storage position of data stored in a memory,
Address generation means for continuously generating all the basic addresses that can be expressed by a predetermined bit length by changing the value by 1;
Address conversion means for generating a first bit string obtained by shifting the basic address by one bit to the right and a second bit string obtained by reversing the first bit string for every two basic addresses that differ only in the least significant bit. ,
When the value of the first bit string is equal to or less than the value of the second bit string, a set of the first bit string and the second bit string is determined as a replacement address, and the value of the first bit string is An address adjusting means for determining, as the replacement address, a set of bit strings obtained by logically inverting the first bit string and the second bit string, respectively, when the value is larger than the value of the second bit string;
Data replacement means for replacing the storage positions of two data in the memory specified by the replacement address each time the replacement address is determined;
A data position conversion device comprising: When a fixed bit length indicating an offset portion is set in advance, the address conversion unit uses the bit string obtained by deleting the fixed bit length from the upper bits of the basic address instead of the basic address. Generating a bit string and the second bit string;
The address adjusting means adds the fixed bit length bit string deleted by the address converting means to the higher order of the set of bit strings determined as the replacement address, respectively.
The data position conversion apparatus according to claim 1, wherein: In a data position conversion method for converting the storage position of data stored in a memory,
The address generation means continuously generates all the basic addresses that can be expressed by a predetermined bit length by changing the value by 1.
The address conversion unit generates, for each of the two basic addresses that differ only in the least significant bit, a first bit string obtained by shifting the basic address to the right by one bit and a second bit string obtained by reversing the first bit string. And
When the value of the first bit string is less than or equal to the value of the second bit string, the address adjustment unit determines that the combination of the first bit string and the second bit string is a replacement address, and the first bit string When the value of the bit string is larger than the value of the second bit string, a set of bit strings obtained by logically inverting the first bit string and the second bit string is determined as the replacement address;
Each time the replacement address is determined, the data replacement means replaces the storage positions of the two data in the memory specified by the replacement address.
A data position conversion method characterized by that.

Images