Circular CAN IDs list with dynamic compression and CAN context dynamic changing
of IDs -> Cyber Security: Suppression of CAN messages
- use CAN & CAN FD
- use r0,r1/res reserved bits from Control Field
- use a simple arithmetic compression algorithm (better than RLE based on Calkin
Wilf tree)
- ECU with freeze frame data buffers which will store the IDs of an ECU which leave
or enter the communication
- security mechanism guaranteed by the fact that IDs are changed dynamic with the
context of the bus
Implies changes only the SW CAN task.
Compress only messages with a very long sequence of bits with the same value (ie
64 bits of 0 will be compressed by using the value of the fraction obtained visiting the Calkin-Wilf tree so 1/63; 1/63 will be stored using 7 bits for 1 and 7 bits for 63 -
so 14 instead 64).
Such messages will have the CAN ControlField reserved bits set at the beginning
with a fixed value which can be in time also changed via a known swapping values
mechanism.
Also the layout of bits inside such message can be circular shifted with the same
value.
63 will mean that after a sequence of 63 messages which can be again compressed
each ECU will swap using a circular mechanism the IDs for their messages.
All ECU will have the arbitration phase done more complex - each ECU will know the
real ID but using an array will store the new values.
At the begging of communication the values like 63 will be very frequent because
most of delault/init values from DBCs are with min/max values.
I.e. Motor message will have at the beginning in the DBC the CAN ID 0x10.
After 63 messages that can be compressed each ECU so also the Motor ECU will
circular shift all values of IDs with 1 position (or 63 positions).
Instead of sending the value 0x10 the Motor ECU will send it's message with a new
ID - eg 0x0F or 0x11 it depends on the direction chosen to be used for circular
shifting.
The value 63 will be used like a new XOR mask with all the bytes from each message
also CRC bits also stuffing bits, till a new value will be determined from a message
that can be again compressed.
When an ECU wants go PowerReducion it will just stop communication at the CAN
level transmission.
When an ECU want to restore from PowerReduction in the CAN communication will
send a special message with initial ID from DBC and last known ID known after last
circular shift of IDs for 2/3 times.
At this moment all ECU will receive this message and will re-init the process with
last known values of IDs -> IDs shifted with the last number of compression done,
known by the ECU that wants to re-enter into the communication.
The compression mechanism will allow each ECU to have time for something else
and the remaining bits can be filled with random values.
In this way the message i.e. 0x10 will be very difficult to be falsified and an
injected 0x10 message will not be interpreted like a valid ID due to the changed ID
arbitration mechanism.
Assures dynamic security - IDs changed dynamically also XOR datas using the
context from the bus.
Can be applied directly from the moment when a new battery is installed in a car and
this process will start with the ECUs which does not have relation with Klemme_15 -
key position.
CAN task and arbitration should be changed - in order to be done on the idexes
of the messages array and not using the values stored there - but sending these
values.
Using circular lists of IDs the values can be mathematical determined and not
necessary searched inside this array.
Saturday, May 12, 2018
Define a Transport Protocol over CAN/ FD for compressing the useful data
Define a Transport Protocol over CAN/ FD for compressing the useful data.
This should be a simple and fast algorithm for both compression/decompression
methods.
From the CAN message structure one of the bits r0 / r1 from the "Control Field" -
bits which "are reserved for future use" - can be used in order to memo if the data
can or cannot be compressed.
https://www.google.ro/search?q=vector+can+protocol+reference+chart
+pdf&biw=1920&bih=979&tbm=isch&tbo=u&source=univ&sa=X&sqi=2&ved=0CEIQsARqFQoTCIvTusjkrcgCFYcYLAodvTUIDg#%3A
In case the data can be compressed then for these message a new byte structure
should be defined.
The first byte of each CAN message should be used in order to memo if the values
can/cannot be compressed and other information all these only for the partial data
not for the cases when a complete message can be compressed in this case this first
byte will store part of the compressed data.
A 1-bit CAN signal can be set in order to show if the values that should be packed in
a message can/cannot be compressed with this algorithm.
A new bit should be used in order to specify if all data from a message or only a part
of it can be compressed.
In case of only a part of message can be compressed 3 bits + 3 bits should be again
used for storing the byte & bit position + a new byte for storing the length of the
compressed sequence.
The algorithm can be an arithmetic method based only on additions - the
compression and substraction - the decompression method.
This algorithm can use the Calkin-Wilf Tree paths(like input from original CAN data)
and generate fractions like compressed information.
This algorithm can be used and produces fractions with nominator and denominator
with less bits that the original path from the tree only for messages with many
0x00/0xFF or paths that can be found on the exterior of the Calkin-Wilf Tree. For
the sequence of bits that form the paths from the interior of this tree so path or
sequence of bits like 010101010101.. there is no gain achieved by this compression
method.
Using this fast & simple compression/decompression algorithm also the CAN
arbitration phase can be changed in order to take into account if the compressed
data are completely finished or not.
In case the compressed data was sent and it's length is less than 8 bytes during
the remaining bits that remained - so not relevant, a new arbitration phase can be
started and some speed of the entire communication can also be gained in such
cases.
Also using a compression method for the CAN data an other approach can be the
possibility to add multiplexed values so new signals on the positions gained with the
compression.
ECU can decompress and send at Vehicle CAN the un-compressed messages.
In this way the overall communication between ECUs can be increased in speed.
This should be a simple and fast algorithm for both compression/decompression
methods.
From the CAN message structure one of the bits r0 / r1 from the "Control Field" -
bits which "are reserved for future use" - can be used in order to memo if the data
can or cannot be compressed.
https://www.google.ro/search?q=vector+can+protocol+reference+chart
+pdf&biw=1920&bih=979&tbm=isch&tbo=u&source=univ&sa=X&sqi=2&ved=0CEIQsARqFQoTCIvTusjkrcgCFYcYLAodvTUIDg#%3A
In case the data can be compressed then for these message a new byte structure
should be defined.
The first byte of each CAN message should be used in order to memo if the values
can/cannot be compressed and other information all these only for the partial data
not for the cases when a complete message can be compressed in this case this first
byte will store part of the compressed data.
A 1-bit CAN signal can be set in order to show if the values that should be packed in
a message can/cannot be compressed with this algorithm.
A new bit should be used in order to specify if all data from a message or only a part
of it can be compressed.
In case of only a part of message can be compressed 3 bits + 3 bits should be again
used for storing the byte & bit position + a new byte for storing the length of the
compressed sequence.
The algorithm can be an arithmetic method based only on additions - the
compression and substraction - the decompression method.
This algorithm can use the Calkin-Wilf Tree paths(like input from original CAN data)
and generate fractions like compressed information.
This algorithm can be used and produces fractions with nominator and denominator
with less bits that the original path from the tree only for messages with many
0x00/0xFF or paths that can be found on the exterior of the Calkin-Wilf Tree. For
the sequence of bits that form the paths from the interior of this tree so path or
sequence of bits like 010101010101.. there is no gain achieved by this compression
method.
Using this fast & simple compression/decompression algorithm also the CAN
arbitration phase can be changed in order to take into account if the compressed
data are completely finished or not.
In case the compressed data was sent and it's length is less than 8 bytes during
the remaining bits that remained - so not relevant, a new arbitration phase can be
started and some speed of the entire communication can also be gained in such
cases.
Also using a compression method for the CAN data an other approach can be the
possibility to add multiplexed values so new signals on the positions gained with the
compression.
ECU can decompress and send at Vehicle CAN the un-compressed messages.
In this way the overall communication between ECUs can be increased in speed.
Saturday, November 17, 2012
Tuesday, August 28, 2012
ALU macros and splitting a formula
It is interesting to study all combinations between + and binary operators in order to see if complex/big parts from a formula can be split and for operations to be used exactly these macros of simple operations.
Sunday, December 20, 2009
Cryptographic circuit
The ideas of these lines came by taking into consideration the way that modern servers convert the code of the web pages, showing to the users only a slide interpreted in the HTML language; in this way the code and the algorithms are not accessible - see for example how this machanism is implemented in the PHP language.
This proposed cryptographic circuit has to take the role of the PHP language making hidden to the users the code that is running on the CPU.
How this circuit has to work is similar to the way of crypting with two locks but it will use instead of these locks some internal registers which to not be accessible to the users.
All the executable codes have to be converted using a generic language and a table in which are stored the correspondences between these new generic operators and the common ones from the ASM language.
The circuit will have the role to update the content of the internal registers proposed with the new correspondence and will make also the link to the HW.
In this way the code that is executed will not be accessible to the common users and some parts of programs (serial numbers of the setups) can be easily very good protected.
With this kind of circuit any activity of programs like macros recording > recording/merging macros from any application - can be avoided.
This proposed cryptographic circuit has to take the role of the PHP language making hidden to the users the code that is running on the CPU.
How this circuit has to work is similar to the way of crypting with two locks but it will use instead of these locks some internal registers which to not be accessible to the users.
All the executable codes have to be converted using a generic language and a table in which are stored the correspondences between these new generic operators and the common ones from the ASM language.
The circuit will have the role to update the content of the internal registers proposed with the new correspondence and will make also the link to the HW.
In this way the code that is executed will not be accessible to the common users and some parts of programs (serial numbers of the setups) can be easily very good protected.
With this kind of circuit any activity of programs like macros recording > recording/merging macros from any application - can be avoided.
Thursday, December 3, 2009
ALU ADD Circuit
The basic for this proposal is the classic circuit of adding two numbers on multiple bits.
Looking into the 2 dimensional array of the obtained appling the binary XOR operation on the bits of all the pairs of numbers smaller than a number it can be seen that instead of doing a+b (a and b are decimal numbres) we can do:
x= a xor b
y= 2*(a and b) and in approx. 50%, a+b = x or y and in the other 50% a+b = x+y this mean that we have to introduce again x and y in the ADD circuit.
If we draw the circuit only for adding 2 bits x and y to be introduced in the circuit means to apply some XOR gates to the binary representation of them.
The basic idea of this disclosure is focused on the 50% of cases in which a+b = x or y.
For this I formed a circuit in Tina ver. 6.0 a model of circuit that uses tri state buffers for selecting the cases when we have to use the XOR gates or the OR gates; instead of using a 3 state buffers there can be usesed one transistor.
In this way we avoid the usage of the XOR gates using only 1 transistors for each bit/line and OR gates.
In this way the timeof computing wll be faster and only the energy consume will be lower, beacuse of using less number of transistors.
ALU ADD Circuit, C Program source code
#include
#include
# include
# define MAX 32
FILE * pf;
int i, j;
int contor = 0;
int total = 0;
int rez;
void f(int x, int y)
{
fprintf(pf,"%3d + %3d = %3d + %3d",x,y, (x^y), 2*(x&y));
//fprintf(pf,"%3d ",x+y - ((x^y) | (2*(x&y))));
total ++;
if( ((x^y) + (2*(x&y))) == ((x^y) | (2*(x&y))) )
contor ++;
}
void main(void)
{
pf=fopen("c:\\xor.txt","w+");
for(i=0;i
fprintf(pf,"\n");
for(j=0;j
}
fcloseall();
printf("TOTAL = %d\n",total);
printf("OPTIMIZED = %d\n",contor);
printf("PERCENTAGE = %5.2f\n",(float)(contor)/(float)(total/100));
}
0 + 0 = 0 + 0 0 + 1 = 1 + 0 0 + 2 = 2 + 0 0 + 3 = 3 + 0 0 + 4 = 4 + 0 0 + 5 = 5 + 0 0 + 6 = 6 + 0 0 + 7 = 7 + 0 0 + 8 = 8 + 0 0 + 9 = 9 + 0 0 + 10 = 10 + 0 0 + 11 = 11 + 0 0 + 12 = 12 + 0 0 + 13 = 13 + 0 0 + 14 = 14 + 0 0 + 15 = 15 + 0 0 + 16 = 16 + 0 0 + 17 = 17 + 0 0 + 18 = 18 + 0 0 + 19 = 19 + 0 0 + 20 = 20 + 0 0 + 21 = 21 + 0 0 + 22 = 22 + 0 0 + 23 = 23 + 0 0 + 24 = 24 + 0 0 + 25 = 25 + 0 0 + 26 = 26 + 0 0 + 27 = 27 + 0 0 + 28 = 28 + 0 0 + 29 = 29 + 0 0 + 30 = 30 + 0 0 + 31 = 31 + 0
1 + 0 = 1 + 0 1 + 1 = 0 + 2 1 + 2 = 3 + 0 1 + 3 = 2 + 2 1 + 4 = 5 + 0 1 + 5 = 4 + 2 1 + 6 = 7 + 0 1 + 7 = 6 + 2 1 + 8 = 9 + 0 1 + 9 = 8 + 2 1 + 10 = 11 + 0 1 + 11 = 10 + 2 1 + 12 = 13 + 0 1 + 13 = 12 + 2 1 + 14 = 15 + 0 1 + 15 = 14 + 2 1 + 16 = 17 + 0 1 + 17 = 16 + 2 1 + 18 = 19 + 0 1 + 19 = 18 + 2 1 + 20 = 21 + 0 1 + 21 = 20 + 2 1 + 22 = 23 + 0 1 + 23 = 22 + 2 1 + 24 = 25 + 0 1 + 25 = 24 + 2 1 + 26 = 27 + 0 1 + 27 = 26 + 2 1 + 28 = 29 + 0 1 + 29 = 28 + 2 1 + 30 = 31 + 0 1 + 31 = 30 + 2
2 + 0 = 2 + 0 2 + 1 = 3 + 0 2 + 2 = 0 + 4 2 + 3 = 1 + 4 2 + 4 = 6 + 0 2 + 5 = 7 + 0 2 + 6 = 4 + 4 2 + 7 = 5 + 4 2 + 8 = 10 + 0 2 + 9 = 11 + 0 2 + 10 = 8 + 4 2 + 11 = 9 + 4 2 + 12 = 14 + 0 2 + 13 = 15 + 0 2 + 14 = 12 + 4 2 + 15 = 13 + 4 2 + 16 = 18 + 0 2 + 17 = 19 + 0 2 + 18 = 16 + 4 2 + 19 = 17 + 4 2 + 20 = 22 + 0 2 + 21 = 23 + 0 2 + 22 = 20 + 4 2 + 23 = 21 + 4 2 + 24 = 26 + 0 2 + 25 = 27 + 0 2 + 26 = 24 + 4 2 + 27 = 25 + 4 2 + 28 = 30 + 0 2 + 29 = 31 + 0 2 + 30 = 28 + 4 2 + 31 = 29 + 4
3 + 0 = 3 + 0 3 + 1 = 2 + 2 3 + 2 = 1 + 4 3 + 3 = 0 + 6 3 + 4 = 7 + 0 3 + 5 = 6 + 2 3 + 6 = 5 + 4 3 + 7 = 4 + 6 3 + 8 = 11 + 0 3 + 9 = 10 + 2 3 + 10 = 9 + 4 3 + 11 = 8 + 6 3 + 12 = 15 + 0 3 + 13 = 14 + 2 3 + 14 = 13 + 4 3 + 15 = 12 + 6 3 + 16 = 19 + 0 3 + 17 = 18 + 2 3 + 18 = 17 + 4 3 + 19 = 16 + 6 3 + 20 = 23 + 0 3 + 21 = 22 + 2 3 + 22 = 21 + 4 3 + 23 = 20 + 6 3 + 24 = 27 + 0 3 + 25 = 26 + 2 3 + 26 = 25 + 4 3 + 27 = 24 + 6 3 + 28 = 31 + 0 3 + 29 = 30 + 2 3 + 30 = 29 + 4 3 + 31 = 28 + 6
4 + 0 = 4 + 0 4 + 1 = 5 + 0 4 + 2 = 6 + 0 4 + 3 = 7 + 0 4 + 4 = 0 + 8 4 + 5 = 1 + 8 4 + 6 = 2 + 8 4 + 7 = 3 + 8 4 + 8 = 12 + 0 4 + 9 = 13 + 0 4 + 10 = 14 + 0 4 + 11 = 15 + 0 4 + 12 = 8 + 8 4 + 13 = 9 + 8 4 + 14 = 10 + 8 4 + 15 = 11 + 8 4 + 16 = 20 + 0 4 + 17 = 21 + 0 4 + 18 = 22 + 0 4 + 19 = 23 + 0 4 + 20 = 16 + 8 4 + 21 = 17 + 8 4 + 22 = 18 + 8 4 + 23 = 19 + 8 4 + 24 = 28 + 0 4 + 25 = 29 + 0 4 + 26 = 30 + 0 4 + 27 = 31 + 0 4 + 28 = 24 + 8 4 + 29 = 25 + 8 4 + 30 = 26 + 8 4 + 31 = 27 + 8
5 + 0 = 5 + 0 5 + 1 = 4 + 2 5 + 2 = 7 + 0 5 + 3 = 6 + 2 5 + 4 = 1 + 8 5 + 5 = 0 + 10 5 + 6 = 3 + 8 5 + 7 = 2 + 10 5 + 8 = 13 + 0 5 + 9 = 12 + 2 5 + 10 = 15 + 0 5 + 11 = 14 + 2 5 + 12 = 9 + 8 5 + 13 = 8 + 10 5 + 14 = 11 + 8 5 + 15 = 10 + 10 5 + 16 = 21 + 0 5 + 17 = 20 + 2 5 + 18 = 23 + 0 5 + 19 = 22 + 2 5 + 20 = 17 + 8 5 + 21 = 16 + 10 5 + 22 = 19 + 8 5 + 23 = 18 + 10 5 + 24 = 29 + 0 5 + 25 = 28 + 2 5 + 26 = 31 + 0 5 + 27 = 30 + 2 5 + 28 = 25 + 8 5 + 29 = 24 + 10 5 + 30 = 27 + 8 5 + 31 = 26 + 10
6 + 0 = 6 + 0 6 + 1 = 7 + 0 6 + 2 = 4 + 4 6 + 3 = 5 + 4 6 + 4 = 2 + 8 6 + 5 = 3 + 8 6 + 6 = 0 + 12 6 + 7 = 1 + 12 6 + 8 = 14 + 0 6 + 9 = 15 + 0 6 + 10 = 12 + 4 6 + 11 = 13 + 4 6 + 12 = 10 + 8 6 + 13 = 11 + 8 6 + 14 = 8 + 12 6 + 15 = 9 + 12 6 + 16 = 22 + 0 6 + 17 = 23 + 0 6 + 18 = 20 + 4 6 + 19 = 21 + 4 6 + 20 = 18 + 8 6 + 21 = 19 + 8 6 + 22 = 16 + 12 6 + 23 = 17 + 12 6 + 24 = 30 + 0 6 + 25 = 31 + 0 6 + 26 = 28 + 4 6 + 27 = 29 + 4 6 + 28 = 26 + 8 6 + 29 = 27 + 8 6 + 30 = 24 + 12 6 + 31 = 25 + 12
7 + 0 = 7 + 0 7 + 1 = 6 + 2 7 + 2 = 5 + 4 7 + 3 = 4 + 6 7 + 4 = 3 + 8 7 + 5 = 2 + 10 7 + 6 = 1 + 12 7 + 7 = 0 + 14 7 + 8 = 15 + 0 7 + 9 = 14 + 2 7 + 10 = 13 + 4 7 + 11 = 12 + 6 7 + 12 = 11 + 8 7 + 13 = 10 + 10 7 + 14 = 9 + 12 7 + 15 = 8 + 14 7 + 16 = 23 + 0 7 + 17 = 22 + 2 7 + 18 = 21 + 4 7 + 19 = 20 + 6 7 + 20 = 19 + 8 7 + 21 = 18 + 10 7 + 22 = 17 + 12 7 + 23 = 16 + 14 7 + 24 = 31 + 0 7 + 25 = 30 + 2 7 + 26 = 29 + 4 7 + 27 = 28 + 6 7 + 28 = 27 + 8 7 + 29 = 26 + 10 7 + 30 = 25 + 12 7 + 31 = 24 + 14
8 + 0 = 8 + 0 8 + 1 = 9 + 0 8 + 2 = 10 + 0 8 + 3 = 11 + 0 8 + 4 = 12 + 0 8 + 5 = 13 + 0 8 + 6 = 14 + 0 8 + 7 = 15 + 0 8 + 8 = 0 + 16 8 + 9 = 1 + 16 8 + 10 = 2 + 16 8 + 11 = 3 + 16 8 + 12 = 4 + 16 8 + 13 = 5 + 16 8 + 14 = 6 + 16 8 + 15 = 7 + 16 8 + 16 = 24 + 0 8 + 17 = 25 + 0 8 + 18 = 26 + 0 8 + 19 = 27 + 0 8 + 20 = 28 + 0 8 + 21 = 29 + 0 8 + 22 = 30 + 0 8 + 23 = 31 + 0 8 + 24 = 16 + 16 8 + 25 = 17 + 16 8 + 26 = 18 + 16 8 + 27 = 19 + 16 8 + 28 = 20 + 16 8 + 29 = 21 + 16 8 + 30 = 22 + 16 8 + 31 = 23 + 16
9 + 0 = 9 + 0 9 + 1 = 8 + 2 9 + 2 = 11 + 0 9 + 3 = 10 + 2 9 + 4 = 13 + 0 9 + 5 = 12 + 2 9 + 6 = 15 + 0 9 + 7 = 14 + 2 9 + 8 = 1 + 16 9 + 9 = 0 + 18 9 + 10 = 3 + 16 9 + 11 = 2 + 18 9 + 12 = 5 + 16 9 + 13 = 4 + 18 9 + 14 = 7 + 16 9 + 15 = 6 + 18 9 + 16 = 25 + 0 9 + 17 = 24 + 2 9 + 18 = 27 + 0 9 + 19 = 26 + 2 9 + 20 = 29 + 0 9 + 21 = 28 + 2 9 + 22 = 31 + 0 9 + 23 = 30 + 2 9 + 24 = 17 + 16 9 + 25 = 16 + 18 9 + 26 = 19 + 16 9 + 27 = 18 + 18 9 + 28 = 21 + 16 9 + 29 = 20 + 18 9 + 30 = 23 + 16 9 + 31 = 22 + 18
10 + 0 = 10 + 0 10 + 1 = 11 + 0 10 + 2 = 8 + 4 10 + 3 = 9 + 4 10 + 4 = 14 + 0 10 + 5 = 15 + 0 10 + 6 = 12 + 4 10 + 7 = 13 + 4 10 + 8 = 2 + 16 10 + 9 = 3 + 16 10 + 10 = 0 + 20 10 + 11 = 1 + 20 10 + 12 = 6 + 16 10 + 13 = 7 + 16 10 + 14 = 4 + 20 10 + 15 = 5 + 20 10 + 16 = 26 + 0 10 + 17 = 27 + 0 10 + 18 = 24 + 4 10 + 19 = 25 + 4 10 + 20 = 30 + 0 10 + 21 = 31 + 0 10 + 22 = 28 + 4 10 + 23 = 29 + 4 10 + 24 = 18 + 16 10 + 25 = 19 + 16 10 + 26 = 16 + 20 10 + 27 = 17 + 20 10 + 28 = 22 + 16 10 + 29 = 23 + 16 10 + 30 = 20 + 20 10 + 31 = 21 + 20
11 + 0 = 11 + 0 11 + 1 = 10 + 2 11 + 2 = 9 + 4 11 + 3 = 8 + 6 11 + 4 = 15 + 0 11 + 5 = 14 + 2 11 + 6 = 13 + 4 11 + 7 = 12 + 6 11 + 8 = 3 + 16 11 + 9 = 2 + 18 11 + 10 = 1 + 20 11 + 11 = 0 + 22 11 + 12 = 7 + 16 11 + 13 = 6 + 18 11 + 14 = 5 + 20 11 + 15 = 4 + 22 11 + 16 = 27 + 0 11 + 17 = 26 + 2 11 + 18 = 25 + 4 11 + 19 = 24 + 6 11 + 20 = 31 + 0 11 + 21 = 30 + 2 11 + 22 = 29 + 4 11 + 23 = 28 + 6 11 + 24 = 19 + 16 11 + 25 = 18 + 18 11 + 26 = 17 + 20 11 + 27 = 16 + 22 11 + 28 = 23 + 16 11 + 29 = 22 + 18 11 + 30 = 21 + 20 11 + 31 = 20 + 22
12 + 0 = 12 + 0 12 + 1 = 13 + 0 12 + 2 = 14 + 0 12 + 3 = 15 + 0 12 + 4 = 8 + 8 12 + 5 = 9 + 8 12 + 6 = 10 + 8 12 + 7 = 11 + 8 12 + 8 = 4 + 16 12 + 9 = 5 + 16 12 + 10 = 6 + 16 12 + 11 = 7 + 16 12 + 12 = 0 + 24 12 + 13 = 1 + 24 12 + 14 = 2 + 24 12 + 15 = 3 + 24 12 + 16 = 28 + 0 12 + 17 = 29 + 0 12 + 18 = 30 + 0 12 + 19 = 31 + 0 12 + 20 = 24 + 8 12 + 21 = 25 + 8 12 + 22 = 26 + 8 12 + 23 = 27 + 8 12 + 24 = 20 + 16 12 + 25 = 21 + 16 12 + 26 = 22 + 16 12 + 27 = 23 + 16 12 + 28 = 16 + 24 12 + 29 = 17 + 24 12 + 30 = 18 + 24 12 + 31 = 19 + 24
13 + 0 = 13 + 0 13 + 1 = 12 + 2 13 + 2 = 15 + 0 13 + 3 = 14 + 2 13 + 4 = 9 + 8 13 + 5 = 8 + 10 13 + 6 = 11 + 8 13 + 7 = 10 + 10 13 + 8 = 5 + 16 13 + 9 = 4 + 18 13 + 10 = 7 + 16 13 + 11 = 6 + 18 13 + 12 = 1 + 24 13 + 13 = 0 + 26 13 + 14 = 3 + 24 13 + 15 = 2 + 26 13 + 16 = 29 + 0 13 + 17 = 28 + 2 13 + 18 = 31 + 0 13 + 19 = 30 + 2 13 + 20 = 25 + 8 13 + 21 = 24 + 10 13 + 22 = 27 + 8 13 + 23 = 26 + 10 13 + 24 = 21 + 16 13 + 25 = 20 + 18 13 + 26 = 23 + 16 13 + 27 = 22 + 18 13 + 28 = 17 + 24 13 + 29 = 16 + 26 13 + 30 = 19 + 24 13 + 31 = 18 + 26
14 + 0 = 14 + 0 14 + 1 = 15 + 0 14 + 2 = 12 + 4 14 + 3 = 13 + 4 14 + 4 = 10 + 8 14 + 5 = 11 + 8 14 + 6 = 8 + 12 14 + 7 = 9 + 12 14 + 8 = 6 + 16 14 + 9 = 7 + 16 14 + 10 = 4 + 20 14 + 11 = 5 + 20 14 + 12 = 2 + 24 14 + 13 = 3 + 24 14 + 14 = 0 + 28 14 + 15 = 1 + 28 14 + 16 = 30 + 0 14 + 17 = 31 + 0 14 + 18 = 28 + 4 14 + 19 = 29 + 4 14 + 20 = 26 + 8 14 + 21 = 27 + 8 14 + 22 = 24 + 12 14 + 23 = 25 + 12 14 + 24 = 22 + 16 14 + 25 = 23 + 16 14 + 26 = 20 + 20 14 + 27 = 21 + 20 14 + 28 = 18 + 24 14 + 29 = 19 + 24 14 + 30 = 16 + 28 14 + 31 = 17 + 28
15 + 0 = 15 + 0 15 + 1 = 14 + 2 15 + 2 = 13 + 4 15 + 3 = 12 + 6 15 + 4 = 11 + 8 15 + 5 = 10 + 10 15 + 6 = 9 + 12 15 + 7 = 8 + 14 15 + 8 = 7 + 16 15 + 9 = 6 + 18 15 + 10 = 5 + 20 15 + 11 = 4 + 22 15 + 12 = 3 + 24 15 + 13 = 2 + 26 15 + 14 = 1 + 28 15 + 15 = 0 + 30 15 + 16 = 31 + 0 15 + 17 = 30 + 2 15 + 18 = 29 + 4 15 + 19 = 28 + 6 15 + 20 = 27 + 8 15 + 21 = 26 + 10 15 + 22 = 25 + 12 15 + 23 = 24 + 14 15 + 24 = 23 + 16 15 + 25 = 22 + 18 15 + 26 = 21 + 20 15 + 27 = 20 + 22 15 + 28 = 19 + 24 15 + 29 = 18 + 26 15 + 30 = 17 + 28 15 + 31 = 16 + 30
16 + 0 = 16 + 0 16 + 1 = 17 + 0 16 + 2 = 18 + 0 16 + 3 = 19 + 0 16 + 4 = 20 + 0 16 + 5 = 21 + 0 16 + 6 = 22 + 0 16 + 7 = 23 + 0 16 + 8 = 24 + 0 16 + 9 = 25 + 0 16 + 10 = 26 + 0 16 + 11 = 27 + 0 16 + 12 = 28 + 0 16 + 13 = 29 + 0 16 + 14 = 30 + 0 16 + 15 = 31 + 0 16 + 16 = 0 + 32 16 + 17 = 1 + 32 16 + 18 = 2 + 32 16 + 19 = 3 + 32 16 + 20 = 4 + 32 16 + 21 = 5 + 32 16 + 22 = 6 + 32 16 + 23 = 7 + 32 16 + 24 = 8 + 32 16 + 25 = 9 + 32 16 + 26 = 10 + 32 16 + 27 = 11 + 32 16 + 28 = 12 + 32 16 + 29 = 13 + 32 16 + 30 = 14 + 32 16 + 31 = 15 + 32
17 + 0 = 17 + 0 17 + 1 = 16 + 2 17 + 2 = 19 + 0 17 + 3 = 18 + 2 17 + 4 = 21 + 0 17 + 5 = 20 + 2 17 + 6 = 23 + 0 17 + 7 = 22 + 2 17 + 8 = 25 + 0 17 + 9 = 24 + 2 17 + 10 = 27 + 0 17 + 11 = 26 + 2 17 + 12 = 29 + 0 17 + 13 = 28 + 2 17 + 14 = 31 + 0 17 + 15 = 30 + 2 17 + 16 = 1 + 32 17 + 17 = 0 + 34 17 + 18 = 3 + 32 17 + 19 = 2 + 34 17 + 20 = 5 + 32 17 + 21 = 4 + 34 17 + 22 = 7 + 32 17 + 23 = 6 + 34 17 + 24 = 9 + 32 17 + 25 = 8 + 34 17 + 26 = 11 + 32 17 + 27 = 10 + 34 17 + 28 = 13 + 32 17 + 29 = 12 + 34 17 + 30 = 15 + 32 17 + 31 = 14 + 34
18 + 0 = 18 + 0 18 + 1 = 19 + 0 18 + 2 = 16 + 4 18 + 3 = 17 + 4 18 + 4 = 22 + 0 18 + 5 = 23 + 0 18 + 6 = 20 + 4 18 + 7 = 21 + 4 18 + 8 = 26 + 0 18 + 9 = 27 + 0 18 + 10 = 24 + 4 18 + 11 = 25 + 4 18 + 12 = 30 + 0 18 + 13 = 31 + 0 18 + 14 = 28 + 4 18 + 15 = 29 + 4 18 + 16 = 2 + 32 18 + 17 = 3 + 32 18 + 18 = 0 + 36 18 + 19 = 1 + 36 18 + 20 = 6 + 32 18 + 21 = 7 + 32 18 + 22 = 4 + 36 18 + 23 = 5 + 36 18 + 24 = 10 + 32 18 + 25 = 11 + 32 18 + 26 = 8 + 36 18 + 27 = 9 + 36 18 + 28 = 14 + 32 18 + 29 = 15 + 32 18 + 30 = 12 + 36 18 + 31 = 13 + 36
19 + 0 = 19 + 0 19 + 1 = 18 + 2 19 + 2 = 17 + 4 19 + 3 = 16 + 6 19 + 4 = 23 + 0 19 + 5 = 22 + 2 19 + 6 = 21 + 4 19 + 7 = 20 + 6 19 + 8 = 27 + 0 19 + 9 = 26 + 2 19 + 10 = 25 + 4 19 + 11 = 24 + 6 19 + 12 = 31 + 0 19 + 13 = 30 + 2 19 + 14 = 29 + 4 19 + 15 = 28 + 6 19 + 16 = 3 + 32 19 + 17 = 2 + 34 19 + 18 = 1 + 36 19 + 19 = 0 + 38 19 + 20 = 7 + 32 19 + 21 = 6 + 34 19 + 22 = 5 + 36 19 + 23 = 4 + 38 19 + 24 = 11 + 32 19 + 25 = 10 + 34 19 + 26 = 9 + 36 19 + 27 = 8 + 38 19 + 28 = 15 + 32 19 + 29 = 14 + 34 19 + 30 = 13 + 36 19 + 31 = 12 + 38
20 + 0 = 20 + 0 20 + 1 = 21 + 0 20 + 2 = 22 + 0 20 + 3 = 23 + 0 20 + 4 = 16 + 8 20 + 5 = 17 + 8 20 + 6 = 18 + 8 20 + 7 = 19 + 8 20 + 8 = 28 + 0 20 + 9 = 29 + 0 20 + 10 = 30 + 0 20 + 11 = 31 + 0 20 + 12 = 24 + 8 20 + 13 = 25 + 8 20 + 14 = 26 + 8 20 + 15 = 27 + 8 20 + 16 = 4 + 32 20 + 17 = 5 + 32 20 + 18 = 6 + 32 20 + 19 = 7 + 32 20 + 20 = 0 + 40 20 + 21 = 1 + 40 20 + 22 = 2 + 40 20 + 23 = 3 + 40 20 + 24 = 12 + 32 20 + 25 = 13 + 32 20 + 26 = 14 + 32 20 + 27 = 15 + 32 20 + 28 = 8 + 40 20 + 29 = 9 + 40 20 + 30 = 10 + 40 20 + 31 = 11 + 40
21 + 0 = 21 + 0 21 + 1 = 20 + 2 21 + 2 = 23 + 0 21 + 3 = 22 + 2 21 + 4 = 17 + 8 21 + 5 = 16 + 10 21 + 6 = 19 + 8 21 + 7 = 18 + 10 21 + 8 = 29 + 0 21 + 9 = 28 + 2 21 + 10 = 31 + 0 21 + 11 = 30 + 2 21 + 12 = 25 + 8 21 + 13 = 24 + 10 21 + 14 = 27 + 8 21 + 15 = 26 + 10 21 + 16 = 5 + 32 21 + 17 = 4 + 34 21 + 18 = 7 + 32 21 + 19 = 6 + 34 21 + 20 = 1 + 40 21 + 21 = 0 + 42 21 + 22 = 3 + 40 21 + 23 = 2 + 42 21 + 24 = 13 + 32 21 + 25 = 12 + 34 21 + 26 = 15 + 32 21 + 27 = 14 + 34 21 + 28 = 9 + 40 21 + 29 = 8 + 42 21 + 30 = 11 + 40 21 + 31 = 10 + 42
22 + 0 = 22 + 0 22 + 1 = 23 + 0 22 + 2 = 20 + 4 22 + 3 = 21 + 4 22 + 4 = 18 + 8 22 + 5 = 19 + 8 22 + 6 = 16 + 12 22 + 7 = 17 + 12 22 + 8 = 30 + 0 22 + 9 = 31 + 0 22 + 10 = 28 + 4 22 + 11 = 29 + 4 22 + 12 = 26 + 8 22 + 13 = 27 + 8 22 + 14 = 24 + 12 22 + 15 = 25 + 12 22 + 16 = 6 + 32 22 + 17 = 7 + 32 22 + 18 = 4 + 36 22 + 19 = 5 + 36 22 + 20 = 2 + 40 22 + 21 = 3 + 40 22 + 22 = 0 + 44 22 + 23 = 1 + 44 22 + 24 = 14 + 32 22 + 25 = 15 + 32 22 + 26 = 12 + 36 22 + 27 = 13 + 36 22 + 28 = 10 + 40 22 + 29 = 11 + 40 22 + 30 = 8 + 44 22 + 31 = 9 + 44
23 + 0 = 23 + 0 23 + 1 = 22 + 2 23 + 2 = 21 + 4 23 + 3 = 20 + 6 23 + 4 = 19 + 8 23 + 5 = 18 + 10 23 + 6 = 17 + 12 23 + 7 = 16 + 14 23 + 8 = 31 + 0 23 + 9 = 30 + 2 23 + 10 = 29 + 4 23 + 11 = 28 + 6 23 + 12 = 27 + 8 23 + 13 = 26 + 10 23 + 14 = 25 + 12 23 + 15 = 24 + 14 23 + 16 = 7 + 32 23 + 17 = 6 + 34 23 + 18 = 5 + 36 23 + 19 = 4 + 38 23 + 20 = 3 + 40 23 + 21 = 2 + 42 23 + 22 = 1 + 44 23 + 23 = 0 + 46 23 + 24 = 15 + 32 23 + 25 = 14 + 34 23 + 26 = 13 + 36 23 + 27 = 12 + 38 23 + 28 = 11 + 40 23 + 29 = 10 + 42 23 + 30 = 9 + 44 23 + 31 = 8 + 46
24 + 0 = 24 + 0 24 + 1 = 25 + 0 24 + 2 = 26 + 0 24 + 3 = 27 + 0 24 + 4 = 28 + 0 24 + 5 = 29 + 0 24 + 6 = 30 + 0 24 + 7 = 31 + 0 24 + 8 = 16 + 16 24 + 9 = 17 + 16 24 + 10 = 18 + 16 24 + 11 = 19 + 16 24 + 12 = 20 + 16 24 + 13 = 21 + 16 24 + 14 = 22 + 16 24 + 15 = 23 + 16 24 + 16 = 8 + 32 24 + 17 = 9 + 32 24 + 18 = 10 + 32 24 + 19 = 11 + 32 24 + 20 = 12 + 32 24 + 21 = 13 + 32 24 + 22 = 14 + 32 24 + 23 = 15 + 32 24 + 24 = 0 + 48 24 + 25 = 1 + 48 24 + 26 = 2 + 48 24 + 27 = 3 + 48 24 + 28 = 4 + 48 24 + 29 = 5 + 48 24 + 30 = 6 + 48 24 + 31 = 7 + 48
25 + 0 = 25 + 0 25 + 1 = 24 + 2 25 + 2 = 27 + 0 25 + 3 = 26 + 2 25 + 4 = 29 + 0 25 + 5 = 28 + 2 25 + 6 = 31 + 0 25 + 7 = 30 + 2 25 + 8 = 17 + 16 25 + 9 = 16 + 18 25 + 10 = 19 + 16 25 + 11 = 18 + 18 25 + 12 = 21 + 16 25 + 13 = 20 + 18 25 + 14 = 23 + 16 25 + 15 = 22 + 18 25 + 16 = 9 + 32 25 + 17 = 8 + 34 25 + 18 = 11 + 32 25 + 19 = 10 + 34 25 + 20 = 13 + 32 25 + 21 = 12 + 34 25 + 22 = 15 + 32 25 + 23 = 14 + 34 25 + 24 = 1 + 48 25 + 25 = 0 + 50 25 + 26 = 3 + 48 25 + 27 = 2 + 50 25 + 28 = 5 + 48 25 + 29 = 4 + 50 25 + 30 = 7 + 48 25 + 31 = 6 + 50
26 + 0 = 26 + 0 26 + 1 = 27 + 0 26 + 2 = 24 + 4 26 + 3 = 25 + 4 26 + 4 = 30 + 0 26 + 5 = 31 + 0 26 + 6 = 28 + 4 26 + 7 = 29 + 4 26 + 8 = 18 + 16 26 + 9 = 19 + 16 26 + 10 = 16 + 20 26 + 11 = 17 + 20 26 + 12 = 22 + 16 26 + 13 = 23 + 16 26 + 14 = 20 + 20 26 + 15 = 21 + 20 26 + 16 = 10 + 32 26 + 17 = 11 + 32 26 + 18 = 8 + 36 26 + 19 = 9 + 36 26 + 20 = 14 + 32 26 + 21 = 15 + 32 26 + 22 = 12 + 36 26 + 23 = 13 + 36 26 + 24 = 2 + 48 26 + 25 = 3 + 48 26 + 26 = 0 + 52 26 + 27 = 1 + 52 26 + 28 = 6 + 48 26 + 29 = 7 + 48 26 + 30 = 4 + 52 26 + 31 = 5 + 52
27 + 0 = 27 + 0 27 + 1 = 26 + 2 27 + 2 = 25 + 4 27 + 3 = 24 + 6 27 + 4 = 31 + 0 27 + 5 = 30 + 2 27 + 6 = 29 + 4 27 + 7 = 28 + 6 27 + 8 = 19 + 16 27 + 9 = 18 + 18 27 + 10 = 17 + 20 27 + 11 = 16 + 22 27 + 12 = 23 + 16 27 + 13 = 22 + 18 27 + 14 = 21 + 20 27 + 15 = 20 + 22 27 + 16 = 11 + 32 27 + 17 = 10 + 34 27 + 18 = 9 + 36 27 + 19 = 8 + 38 27 + 20 = 15 + 32 27 + 21 = 14 + 34 27 + 22 = 13 + 36 27 + 23 = 12 + 38 27 + 24 = 3 + 48 27 + 25 = 2 + 50 27 + 26 = 1 + 52 27 + 27 = 0 + 54 27 + 28 = 7 + 48 27 + 29 = 6 + 50 27 + 30 = 5 + 52 27 + 31 = 4 + 54
28 + 0 = 28 + 0 28 + 1 = 29 + 0 28 + 2 = 30 + 0 28 + 3 = 31 + 0 28 + 4 = 24 + 8 28 + 5 = 25 + 8 28 + 6 = 26 + 8 28 + 7 = 27 + 8 28 + 8 = 20 + 16 28 + 9 = 21 + 16 28 + 10 = 22 + 16 28 + 11 = 23 + 16 28 + 12 = 16 + 24 28 + 13 = 17 + 24 28 + 14 = 18 + 24 28 + 15 = 19 + 24 28 + 16 = 12 + 32 28 + 17 = 13 + 32 28 + 18 = 14 + 32 28 + 19 = 15 + 32 28 + 20 = 8 + 40 28 + 21 = 9 + 40 28 + 22 = 10 + 40 28 + 23 = 11 + 40 28 + 24 = 4 + 48 28 + 25 = 5 + 48 28 + 26 = 6 + 48 28 + 27 = 7 + 48 28 + 28 = 0 + 56 28 + 29 = 1 + 56 28 + 30 = 2 + 56 28 + 31 = 3 + 56
29 + 0 = 29 + 0 29 + 1 = 28 + 2 29 + 2 = 31 + 0 29 + 3 = 30 + 2 29 + 4 = 25 + 8 29 + 5 = 24 + 10 29 + 6 = 27 + 8 29 + 7 = 26 + 10 29 + 8 = 21 + 16 29 + 9 = 20 + 18 29 + 10 = 23 + 16 29 + 11 = 22 + 18 29 + 12 = 17 + 24 29 + 13 = 16 + 26 29 + 14 = 19 + 24 29 + 15 = 18 + 26 29 + 16 = 13 + 32 29 + 17 = 12 + 34 29 + 18 = 15 + 32 29 + 19 = 14 + 34 29 + 20 = 9 + 40 29 + 21 = 8 + 42 29 + 22 = 11 + 40 29 + 23 = 10 + 42 29 + 24 = 5 + 48 29 + 25 = 4 + 50 29 + 26 = 7 + 48 29 + 27 = 6 + 50 29 + 28 = 1 + 56 29 + 29 = 0 + 58 29 + 30 = 3 + 56 29 + 31 = 2 + 58
30 + 0 = 30 + 0 30 + 1 = 31 + 0 30 + 2 = 28 + 4 30 + 3 = 29 + 4 30 + 4 = 26 + 8 30 + 5 = 27 + 8 30 + 6 = 24 + 12 30 + 7 = 25 + 12 30 + 8 = 22 + 16 30 + 9 = 23 + 16 30 + 10 = 20 + 20 30 + 11 = 21 + 20 30 + 12 = 18 + 24 30 + 13 = 19 + 24 30 + 14 = 16 + 28 30 + 15 = 17 + 28 30 + 16 = 14 + 32 30 + 17 = 15 + 32 30 + 18 = 12 + 36 30 + 19 = 13 + 36 30 + 20 = 10 + 40 30 + 21 = 11 + 40 30 + 22 = 8 + 44 30 + 23 = 9 + 44 30 + 24 = 6 + 48 30 + 25 = 7 + 48 30 + 26 = 4 + 52 30 + 27 = 5 + 52 30 + 28 = 2 + 56 30 + 29 = 3 + 56 30 + 30 = 0 + 60 30 + 31 = 1 + 60
31 + 0 = 31 + 0 31 + 1 = 30 + 2 31 + 2 = 29 + 4 31 + 3 = 28 + 6 31 + 4 = 27 + 8 31 + 5 = 26 + 10 31 + 6 = 25 + 12 31 + 7 = 24 + 14 31 + 8 = 23 + 16 31 + 9 = 22 + 18 31 + 10 = 21 + 20 31 + 11 = 20 + 22 31 + 12 = 19 + 24 31 + 13 = 18 + 26 31 + 14 = 17 + 28 31 + 15 = 16 + 30 31 + 16 = 15 + 32 31 + 17 = 14 + 34 31 + 18 = 13 + 36 31 + 19 = 12 + 38 31 + 20 = 11 + 40 31 + 21 = 10 + 42 31 + 22 = 9 + 44 31 + 23 = 8 + 46 31 + 24 = 7 + 48 31 + 25 = 6 + 50 31 + 26 = 5 + 52 31 + 27 = 4 + 54 31 + 28 = 3 + 56 31 + 29 = 2 + 58 31 + 30 = 1 + 60 31 + 31 = 0 + 62
Saturday, July 18, 2009
ALU Cache
This method use some things observered from the fractal world.
If we use the free program: Notepad++ and select a value for the file obtained generating the table: XOR for all the row and column smaller than a value VAL than if we select a value, the program search automatically and highlight the value all over where it can be found.
By doing in this way for some example of values, we can see how the numbers are arranged in the XOR table – in this case on the lines of the Peano filligree:
http://bocut-fractals-appl.blogspot.com/2009/07/xor-peano-filigree.html
We can implement a cache memory for the ALU in wich to store like in a matrix, all these values. Instead of computing an XOR and using 8/16/32 bits a.s.o. we can go directly in this matrix and read the value wich was already calculated.
If we computed for exaple A xor B in the wait time of microprocessor we can calculate all the smaller pairs wich can produce the same result only using an algorthm for bits of A and B.
This is a small C language code to demonstrate that are only necessary to know the representation of numbers A and B – more exactly the length of A and B – only the number of sicnificant bits different than 0 -> without the first positions wich are filled with 0.
http://infoarena.ro/operatii-pe-biti
# include
# include
FILE * pf;
int i,j;
int p,q;
void main(void)
{
pf=fopen(“xor.txt”,”w+”);
for(i=0;i<100 data-blogger-escaped-br="br" data-blogger-escaped-i="i">{
fprintf(pf,”\n\n”);
for(j=0;j<100 data-blogger-escaped-br="br" data-blogger-escaped-j="j"> {
q=(log10(i)/log10(2) < log10(j)/log10(2)) ? (int) log10(j)/log10(2) : log10(i)/log10(2);
++q;
fprintf(pf,”%3d ”, (i^j) – (i – (int)pow(2,q)) ^ (j – (int)pow(2,q)));
}
}
}
From this program it can be see that the only operation wich is made to finding an new pair A’ and B’ wich produce the same result like A xor B is an subtraction with a power of 2; this means that it is enough to negativate the respective bits or to unselect the respective lines when we want to write the result in the new position in the matrix – in memory.
The others binary operation can be verified substarcting (int)pow(2,q) after making an analog substraction like in the program but using instead “^” – xor the respective operator.
In the time when the microprocessor is in the wait state, we can calculte these values.
For numbers that are stored using 8 bits the capacity of the meory will be 2^8 * 2^8 / 2(we divide by 2 because the matrix is simetric after second diagonal) bits so 128 KB.
Instead of calculating on 8 bits an XOR we can just select the line/column from this matrix, step that is already done in the steps of the process of XOR – to fetch the values on the bus.
In this way the speed will grow because let’s say the matrix is complete computing only once and all the time when we want to compute an XOR is necessary only to select the lines without computing the values.
Like a fuel motor, the microprocessor can consume per total lower energy – because the wait states are avoided and like a motor it is not stoped and start again to consume more fuel.
An alternative solution can be the use of an repelace algorithm like in the classic cache memory for xample LRU – Least Recently Used and to have a memory with lower capacity.
ALU cache memory for ADD operations based on AND/XOR fractals
Making an ALU cache for microcontrollers / microprocessors.
Sierpinski fractal applied for XOR operation in a HW cache memory.
This cache memory can be used for both XOR and ADD operations.
XOR and then the complex ADD operations are basic ALU operations.
The total current consumption of uC can decrease. Taking into account that many
operations are currently automated and computers and microcontrollers are almost
present in activities, making a cache for the arithmetic logic unit seems feasible and
can reduce a considerable percentage of computer power consumption.
Making an ALU cache for microcontrollers / microprocessors. The idea resembles the
principle of dynamic programming - that used to shorten recursiveness of functions
in programming -> use a vector to store the results of the recursive function for
cascade calls in order to avoid recursivity if that call was calculated. The project aims
to apply the same principle to HW. It is well known that xor binary operation has at
least 3 different classes of fractals associated. Based on one of these ie. Sierpinski /
Peano can make a logic gateway to calculate and store in idle time of cores thepairs
of numbers that give the same result A xor B. There are other pairs whose results
can be predicted, pairs C xor D whose result based on the mathematical relations
given by the fractals can be directly specified without calculation of xor - for
example, adding powers of 2. With this list of pairs stored in the ALU cache, the
most frequent operations of xor will be avoided to be calculated. While running
a program on a computer, it will check if the N xor M is already cached and will
achieve lower consumption by avoiding memory accesses for 2 operands(featching
N and M) with a simple check if the pair is already cached and in this case 1 single
access to the memory.
OEIS: https://oeis.org/A221146
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 ...
0 0 4 4 0 0 4 4 0 0 4 4 0 0 4 4 ...
0 2 4 6 0 2 4 6 0 2 4 6 0 2 4 6 ...
0 0 0 0 8 8 8 8 0 0 0 0 8 8 8 8 ...
0 2 0 2 8 10 8 10 0 2 0 2 8 10 8 10 ...
0 0 4 4 8 8 12 12 0 0 4 4 8 8 12 12 ...
0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 ...
0 0 0 0 0 0 0 0 16 16 16 16 16 16 16 16 ...
0 2 0 2 0 2 0 2 16 18 16 18 16 18 16 18 ...
0 0 4 4 0 0 4 4 16 16 20 20 16 16 20 20 ...
0 2 4 6 0 2 4 6 16 18 20 22 16 18 20 22 ...
0 0 0 0 8 8 8 8 16 16 16 16 24 24 24 24 ...
0 2 0 2 8 10 8 10 16 18 16 18 24 26 24 26 ...
0 0 4 4 8 8 12 12 16 16 20 20 24 24 28 28 ...
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 ...
...
CROSSREFS
Cf. A003987, A004198.
This matrix is obtained using the addition of the row and column indexes in order
to calculate the XOR between the indexes. The matrix contains the differences that
should be added/substarcted in order to pass from ADD of indexes to XOR of indexes
or vice versa.
This matrix shows the fact that both XOR and ADD operations have the same layout
(using i.e. this fractal) and the ADD operations can be computed easier if XOR is
used based on a cache memory which has implemented in HW this fractal releations.
This mechanism can be used like a lookup table principle in order to avoid the carry
HW logic AND gates, HW complexity inroduced by using AND gates for carry bits.
This lookup table mechanism of having a cache memory using the e.g. Sierpinski
layout will avoid the AND computations and HW complexity.
In this way all these carry bits will be avoided to be calculated using AND gates
and will be "linked" - HW wired or using a HW logic mechanism for all the pairs of
numbers that produce the same results or results that can be predicted.
This linkage will be stored in a cache memory and any future pairs or numbers that
should be added will be first flaged-checked in this cache in order to see if an other
pair of numebrs which has the same fractal propriety/arrangement - the difference
from the matrix of above - was previously calculated.
ALU cache avoids leakage and provides fewer access to memory by reducing
consumption during the calculations A xor B, very often used, used also in additions
which is an important ALU operation for microprocessors / microcontrollers.
Each Matrix operation: Dot Products, matrix multiplications, additions are using the
base addition operation between 2 numbers.
1 Full Adder: 2 XOR, 2 AND, 1 OR gates
1 XOR gate: 2 AND and 2 OR gates
32 Bit Paralle Adder: 31 Full Adders
AND, OR Gates: 3 transistors
1 bit CACHE: 6 trasistors
Classical style = at least 930 transistors
New Style = 32*4*3 + 32 * 6 = 576 transistors + the transistors needed for HW
wired and flaged activation of the values with the same carry result
Power consumption reduction => longer battery life and lower fuel consumption &
emissions in rechanging the battery
If we use the free program: Notepad++ and select a value for the file obtained generating the table: XOR for all the row and column smaller than a value VAL than if we select a value, the program search automatically and highlight the value all over where it can be found.
By doing in this way for some example of values, we can see how the numbers are arranged in the XOR table – in this case on the lines of the Peano filligree:
http://bocut-fractals-appl.blogspot.com/2009/07/xor-peano-filigree.html
We can implement a cache memory for the ALU in wich to store like in a matrix, all these values. Instead of computing an XOR and using 8/16/32 bits a.s.o. we can go directly in this matrix and read the value wich was already calculated.
If we computed for exaple A xor B in the wait time of microprocessor we can calculate all the smaller pairs wich can produce the same result only using an algorthm for bits of A and B.
This is a small C language code to demonstrate that are only necessary to know the representation of numbers A and B – more exactly the length of A and B – only the number of sicnificant bits different than 0 -> without the first positions wich are filled with 0.
http://infoarena.ro/operatii-pe-biti
# include
# include
FILE * pf;
int i,j;
int p,q;
void main(void)
{
pf=fopen(“xor.txt”,”w+”);
for(i=0;i<100 data-blogger-escaped-br="br" data-blogger-escaped-i="i">{
fprintf(pf,”\n\n”);
for(j=0;j<100 data-blogger-escaped-br="br" data-blogger-escaped-j="j"> {
q=(log10(i)/log10(2) < log10(j)/log10(2)) ? (int) log10(j)/log10(2) : log10(i)/log10(2);
++q;
fprintf(pf,”%3d ”, (i^j) – (i – (int)pow(2,q)) ^ (j – (int)pow(2,q)));
}
}
}
From this program it can be see that the only operation wich is made to finding an new pair A’ and B’ wich produce the same result like A xor B is an subtraction with a power of 2; this means that it is enough to negativate the respective bits or to unselect the respective lines when we want to write the result in the new position in the matrix – in memory.
The others binary operation can be verified substarcting (int)pow(2,q) after making an analog substraction like in the program but using instead “^” – xor the respective operator.
In the time when the microprocessor is in the wait state, we can calculte these values.
For numbers that are stored using 8 bits the capacity of the meory will be 2^8 * 2^8 / 2(we divide by 2 because the matrix is simetric after second diagonal) bits so 128 KB.
Instead of calculating on 8 bits an XOR we can just select the line/column from this matrix, step that is already done in the steps of the process of XOR – to fetch the values on the bus.
In this way the speed will grow because let’s say the matrix is complete computing only once and all the time when we want to compute an XOR is necessary only to select the lines without computing the values.
Like a fuel motor, the microprocessor can consume per total lower energy – because the wait states are avoided and like a motor it is not stoped and start again to consume more fuel.
An alternative solution can be the use of an repelace algorithm like in the classic cache memory for xample LRU – Least Recently Used and to have a memory with lower capacity.
Making an ALU cache for microcontrollers / microprocessors.
Sierpinski fractal applied for XOR operation in a HW cache memory.
This cache memory can be used for both XOR and ADD operations.
XOR and then the complex ADD operations are basic ALU operations.
The total current consumption of uC can decrease. Taking into account that many
operations are currently automated and computers and microcontrollers are almost
present in activities, making a cache for the arithmetic logic unit seems feasible and
can reduce a considerable percentage of computer power consumption.
Making an ALU cache for microcontrollers / microprocessors. The idea resembles the
principle of dynamic programming - that used to shorten recursiveness of functions
in programming -> use a vector to store the results of the recursive function for
cascade calls in order to avoid recursivity if that call was calculated. The project aims
to apply the same principle to HW. It is well known that xor binary operation has at
least 3 different classes of fractals associated. Based on one of these ie. Sierpinski /
Peano can make a logic gateway to calculate and store in idle time of cores thepairs
of numbers that give the same result A xor B. There are other pairs whose results
can be predicted, pairs C xor D whose result based on the mathematical relations
given by the fractals can be directly specified without calculation of xor - for
example, adding powers of 2. With this list of pairs stored in the ALU cache, the
most frequent operations of xor will be avoided to be calculated. While running
a program on a computer, it will check if the N xor M is already cached and will
achieve lower consumption by avoiding memory accesses for 2 operands(featching
N and M) with a simple check if the pair is already cached and in this case 1 single
access to the memory.
OEIS: https://oeis.org/A221146
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 ...
0 0 4 4 0 0 4 4 0 0 4 4 0 0 4 4 ...
0 2 4 6 0 2 4 6 0 2 4 6 0 2 4 6 ...
0 0 0 0 8 8 8 8 0 0 0 0 8 8 8 8 ...
0 2 0 2 8 10 8 10 0 2 0 2 8 10 8 10 ...
0 0 4 4 8 8 12 12 0 0 4 4 8 8 12 12 ...
0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 ...
0 0 0 0 0 0 0 0 16 16 16 16 16 16 16 16 ...
0 2 0 2 0 2 0 2 16 18 16 18 16 18 16 18 ...
0 0 4 4 0 0 4 4 16 16 20 20 16 16 20 20 ...
0 2 4 6 0 2 4 6 16 18 20 22 16 18 20 22 ...
0 0 0 0 8 8 8 8 16 16 16 16 24 24 24 24 ...
0 2 0 2 8 10 8 10 16 18 16 18 24 26 24 26 ...
0 0 4 4 8 8 12 12 16 16 20 20 24 24 28 28 ...
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 ...
...
CROSSREFS
Cf. A003987, A004198.
This matrix is obtained using the addition of the row and column indexes in order
to calculate the XOR between the indexes. The matrix contains the differences that
should be added/substarcted in order to pass from ADD of indexes to XOR of indexes
or vice versa.
This matrix shows the fact that both XOR and ADD operations have the same layout
(using i.e. this fractal) and the ADD operations can be computed easier if XOR is
used based on a cache memory which has implemented in HW this fractal releations.
This mechanism can be used like a lookup table principle in order to avoid the carry
HW logic AND gates, HW complexity inroduced by using AND gates for carry bits.
This lookup table mechanism of having a cache memory using the e.g. Sierpinski
layout will avoid the AND computations and HW complexity.
In this way all these carry bits will be avoided to be calculated using AND gates
and will be "linked" - HW wired or using a HW logic mechanism for all the pairs of
numbers that produce the same results or results that can be predicted.
This linkage will be stored in a cache memory and any future pairs or numbers that
should be added will be first flaged-checked in this cache in order to see if an other
pair of numebrs which has the same fractal propriety/arrangement - the difference
from the matrix of above - was previously calculated.
ALU cache avoids leakage and provides fewer access to memory by reducing
consumption during the calculations A xor B, very often used, used also in additions
which is an important ALU operation for microprocessors / microcontrollers.
Each Matrix operation: Dot Products, matrix multiplications, additions are using the
base addition operation between 2 numbers.
1 Full Adder: 2 XOR, 2 AND, 1 OR gates
1 XOR gate: 2 AND and 2 OR gates
32 Bit Paralle Adder: 31 Full Adders
AND, OR Gates: 3 transistors
1 bit CACHE: 6 trasistors
Classical style = at least 930 transistors
New Style = 32*4*3 + 32 * 6 = 576 transistors + the transistors needed for HW
wired and flaged activation of the values with the same carry result
Power consumption reduction => longer battery life and lower fuel consumption &
emissions in rechanging the battery
Subscribe to:
Posts (Atom)
