Algoritmo CORDIC trigonometría.

[Democrito]

Hola,

Acabo de terminar un circuito que calcula el seno y coseno de un ángulo aplicando el algoritmo CORDIC.

Hasta donde yo sé los algoritmos CORDIC dan resultados en punto fijo, en este caso es Q8.8 con signo. 

Patillaje:

ang[15:0] A través de este bus introducimos un número entero sin signo con rango de 0 hasta 360 (inclusive), que es el ángulo el cual queremos conocer el seno y coseno. Para mantener una coherencia en los buses, todos ellos son de 16 bits.

Una vez que le hayamos dado un tic a la patilla start, comenzará el cálculo y cuando termine se producirá un tic por la patilla done.

Los resultados aparecerán por sin[15:0] y cos[15:0] y su vez los signos de éstos aparecerán en los pines signsin y signcos respectivamente.

Al ser formato de punto fijo Q8.8 sólo tenemos dos números como decimales (0.99) y se podría sacar un decimal más, pero como no es posible repartir 256 valores en 999, ese tercer decimal lo omito.

La patilla error se pondrá a 1 cuando se introduzca un número mayor de 360, está limitado a este rango ya que más allá de ese valor dejará de ser preciso. Sobre la precisión, el algoritmo CORDIC es de aproximación y en los peores casos puede cometer un error de 0.1%.

Para probar este circuito adjunto un ejemplo para ver los resultados a través del serial.

Subes el ejemplo y a través del serial introduces cualquier número entero positivo >= de 360º y veremos resultados como estos:

El primer valor es el seno y el segundo valor es el coseno del ángulo introducido.

Observa que en esta última imagen he introducido el valor 361 y el circuito nos responde con "Error!", ya que el valor máximo no ha de superar 360.

El circuito hace lo que esperas de él, pero durante el diseño y pruebas que estuve haciendo tuve que poner algunos parches y lo comento por si alguien se fija en el código verilog de la caja principal. Los senos y cosenos de los ángulos del 1º al 4º no se ajustaban a la realidad y esa parte la parcheé. Por otra parte los ángulos 0, 90, 180, 270 y 360 los parcheé para que dieran valores exactos (0, 1 y -1 según el caso), pero esto es normal hacerlo así ya que hasta con programación es necesario ajustar los resultados para esos ángulos.

De momento no voy a subir este circuito de forma oficial, sólo quedará aquí (de momento) como un ejemplo de algoritmo CORDIC aplicado a senos y cosenos. La razón se debe a que para un formato como Q8.8 creo que consume muchos recursos y saldría más económico y muchísimo más rápido si para este caso (Q8.8) se utilizase una tabla. Para resoluciones mayores de Q8.8 sí puede ser interesante aplicar CORDIC. Como estoy aprendiendo y experimentado en el futuro sabré a ciencia cierta qué es lo mejor que se puede aplicar.

Cualquier cosa que vaya consiguiendo a nivel trigonométrico, mejoras, etc, lo iré publicando en este hilo.

Adjunto módulo y ejemplo.

Saludos.

[Jo mo]

Hola Democrito,

Thanks a lot for sharing your great findings as usual,

If i understood well, for now you have only 360 possible angles (only integers) and 200 possible outputs values(-0.99 to 0.99) so a table of 360 x 8 bits will be more "economic" (as you said )than the CORDIC algorithm!

- if we have 16 bits for the input angle, it can be good to have 9 bits (512 possibilities) for the integer part of the angle and 7 bits for the decimal part !

This will improve the angle precision by a factor of 100, then the calculus/ CORDIC algorithm precision as to follow!

This may make the CORDIC algorithm use more interesting than a look up table solution !

- Maybe we can also subtract 360 to angles greater than 360 (and smaller than 512)! and remove the error output!

I didn't look very in detail on your CORDIC algorithm, but maybe this  pdf  can be of some interest?

Have a nice day!

[Juan Gonzalez Gomez]

¡Muchísimas gracias Demócrito! Lo acabo de probar, y funciona perfecto! La posibilidad de generar senos es tremendamente útil para construir generadores para el movimiento de los robots. Yo es algo que tenía en mente, y cuando me ponga con ello utilizaré tus bloques 😀

Qué gran aportación

Saludos, Obijuan

--
Has recibido este mensaje porque estás suscrito al grupo "FPGAwars: explorando el lado libre" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a fpga-wars-explorando-el...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/fpga-wars-explorando-el-lado-libre/9a63d89b-451e-46c0-b994-7b2790253d47n%40googlegroups.com.

[Democrito]

Obijuan: Tengo pensado poner ejemplos prácticos para usarse tanto en gráficos como en movimientos para motores, pero esto será mucho más adelante. Hace años que este tema lo tenía en la cabeza y la necesidad de crear este tipo de herramientas matemáticas para poder hacer cosas realmente interesantes. Vamos a ello!

Joaquim: Everything you say is so, but it can actually be simplified much more using tables (at least to some extent). It is very easy to know which quadrant an angle is in. So you only need a table of 90 numbers (instead of 360) with the Qx.x resolution you want, but of course, this up to a point.

From 0º to 90º is the base, then in the other quadrants the same numbering is repeated, only the sign changes depending on the quadrant, the only thing that is done is that depending on the quadrant that the angle is and depending on whether it is sine or cosine, it would read table from top to bottom or bottom to top.

The sines and cosines it's correspond, they only complement each other within the table, then, depending on the quadrant, the corresponding sign is placed on it. Example:

sin(0) = cos(90)
sin(30) = cos(60)
sin(45)=cos(45)
sin(60) = cos(30)
sin(90) = cos(0)

In the same way:

sin(0) = cos(90)
sin(1) = cos(89)
sin(2) = cos(88)
sin(3) = cos(87)

...       =    ...

sin(87) = cos(3)

sin(88) = cos(2)

sin(89) = cos(1)

sin(90) = cos(0)

So knowing the quadrant is very simple and then we add the sign that corresponds to that quadrant.

In the integer part we only need a 1 or a 0, and then depending on the quadrant we add the sign.

This means that we can make a Q1.8 (even a Q1.10) for example, without using the famous algorithm, in addition, using tables we would have a maximum calculation speed and an acceptable resource consumption (in comparison).

I keep researching and thinking which is the best option, the important thing is to be able to choose according to the needs that arise and I greatly appreciate your suggestions.

A friendly greeting!

[Jo mo]

Hola Democrito,

School is far away! :-) I still remember about trigonometry !

But as i do not use it every day, a little refresh doesn't arm!   Thanks

For your sine-cordic ice file, the resources used are quite high i found ? 

in the following picture i removed the input and output serial circuits and i stil get 957 LC used  (12,5% on an Alhambra board)

I will also try to get the time to make a sine generator with a table (using only the first quadrant 0 to 90 degree as you suggested! ).

two question in my head:

-  Is it better to divide that quadrant by 64 (6bits),  256(8bits),  or by 90 ( as you did to have a decimal base angle input )

- Will we gain something using radians instead of the human intuitive degrees (special for the Cordic algorythm  version)!

Have a good day!

Joaquim

[Democrito]

-  Is it better to divide that quadrant by 64 (6bits),  256(8bits),  or by 90 ( as you did to have a decimal base angle input )

I don't know Joaquim, it seems logical to me that the more bits the better the resolution. We always come back to the same thing, for 8 bits we have a resolution of 256 possible combinations, therefore 999 would need more bits.

But you make me doubt because, for example, in Bresenham's algorithm it is not necessary to graph 90º, it depends on how you cut "the cake" and then repeat the same thing in the same quadrant and then in the other quadrants.

- We will gain something by using radians instead of human intuitive degrees (special for Cordic algorithm version)!

I also don't know how to give you a sure answer to this question. But I think that electronically it is easier to have a "human" input with sexagesimal degrees, in short, to convert to radians it would only be to multiply by Pi/180 and we already have modules that can divide at a fixed point (I am aware that in this sense it would be add more resources).

I am researching and comparing within my very limited knowledge. We are going to try to release modules that do transcendental mathematical operations and over time create better modules. I believe that if someone understands very well the problem they want to solve and what exists up to now is made available to them, they will be able to carry it out. Let's try to light a spark that starts any project!

I hope you had a restful sleep!

[Jo mo]

" with sexagesimal degrees, "

:-))

Yes Democrito, the important is to start projects, then having fun with them !

Thanks a lot, for bringing us so much matter to think at !

Big hug and have a good evening

[Democrito]

A clarification, where I say "Bresenham algorithm" I meant the same thing but applied to circles. Bresenham's algorithm is often understood to be for lines, but it can be applied to circles, ellipses, etc.

http://members.chello.at/~easyfilter/bresenham.html

In a project I did to do smooth starts and stops (with stepper motors), I used Bresenham's algorithm applied to circles, instead of using a sine function:

Demo video: https://www.youtube.com/watch?v=Oq-1S7Cu5yw (in this project the motor only rotates in one direction)

Thread: https://groups.google.com/g/fpga-wars-explorando-el-lado-libre/c/YvEKFCxXR5Q

Graphic: https://www.youtube.com/watch?v=H7S1Z4wmpyo

Thread:  https://groups.google.com/g/fpga-wars-explorando-el-lado-libre/c/4g2IfOM1kAI/m/z4ko7awHAQAJ

It crossed my mind to use this algorithm to apply it to trigonometry, but the problem is that you have to go through all the points until you reach the desired value. I have not tested it in this sense but when I thought about it I had to discard it by mathematical calculations.

[Democrito]

If someone from the future decides to try the Bresenham algorithm for circumferences (for an OLED) that I published in the thread mentioned above, it will not work because they changed the tools and in the I2C part there is a counter with a reset  input to the air. With the new toolchain this is now not allowed. If someone wants me to correct it, let me know and I'll attach the corrected circuit.

[Democrito]

Acabo de añadir a mi GitHub el cálculo de senos y cosenos utilizando tablas; en esa misma sección también he añadido el CORDIC que puse en post anteriores. Todos los módulos va acompañado de su ejemplo respectivo. De momento todo está para formato Q8.8

https://github.com/Democrito/repositorios/tree/master/Maths/trigonometric/sin_cos (está pendiente completar información e imágenes)

Las tablas se componen de 91 entradas (0..90) y hago trucos (sólo con sumas y restas) para que cualquier entrada dentro del rango 0..360 la tabla apunte al valor que le corresponde, así ahorramos una tabla de 361 elementos por otra de sólo 91.

Cuando consiga hacer un atan2() en formato Q8.8 será entonces cuando añada todos estos módulos a iceArith.

Adjunto los dos ejemplos de tablas aquí por si alguien no sabe descargar los módulos desde GitHub, uno es para calcular el seno y el otro para calcular el coseno.

Saludos.

[Democrito]

Al utilizar tablas sólo se necesita 1 ciclo de reloj, pero para curarme en salud, he utilizado 2 ciclos de reloj.

Adjunto un programa (escrito en FreeBasic) que me ayudó a obtener toda la tabla para el seno y además convertirla a hexadecimal. Una salida de ejemplo es esta:

La primera columna es el ángulo de entrada 0..90.

La segunda columna son los valores en hexadecimal del seno correspondiente al ángulo; este valor está redondeado al alza: Hex(CInt(w*256.0)) Es en hexadecimal porque las tablas de Icestudio sólo acepta, o números hexadecimales o números binarios puros, no es por otro motivo.

La tercera columna son los valores decimales antes de pasarlo a Q8.8, pero en realidad sólo se tiene en cuenta la parte entera.

La cuarta columna es para verificar si los ajustes con redondeo al alza se corresponde con el valor hexadecimal (es para comprobar manualmente que todo está dentro de lo que se espera obtener y las comprobaciones manuales son aleatorias, lo hago con la calculadora).

Ejemplo: busca en la primera columna el número 15 (de 15º), nos da como resultado el valor hexadecimal 42, y 'h42 es 66 en decimal. Si hacemos esta operación a escondidas: 66/256=0.257..., para comprobarlo tomamos la calculadora y hacemos el seno de 15º, nos dará: 0.2588...

Para comprender de dónde vienen las operaciones y cómo se pasa a Q8.8 hay que conocer cómo se pasa un número decimal a Q8.8, así que no te preocupes si no ves la lógica ahora. Cuando me sobre un poco de tiempo tengo pensado hacer un mini-tutorial de cómo pasar de un formato al otro y vice-versa.

El programa también crea un archivo para poder copiar los datos, pero ahí sólo está los hexadecimales, nada más.

Para confeccionar la tabla de cosenos no hace falta volver a hacer esto, sólo hay que invertir la lista de los valores de la tabla (el primero pasarlo al último, el segundo al penúltimo, etc). Utilizo un sitio web que hace esto de forma automática y lo he utilizado en varias ocasiones. Y si os vais a la página principal veréis muchas herramientas útiles para nosotros (electrónicos e informáticos).

Castellano: https://pinetools.com/es/invertir-lista

Inglés: https://pinetools.com/reverse-list

[Jo mo]

Gracias Democrito, for all that wonderful info!

i just tried the resources usage and we have 148 LUT for this table based block (it was 916 for the Cordic version) to get the same precision.

i do not know if it will increase a lot the resources usage, but maybe we can increase the angle precision. by making a linear interpolation after the table!

maybe by doing successive division by 2 of the the difference between 2 values of the table (at the first step).  a bit like the Cordic algorithm but for the fractional part of the angle only!.

Have a nice day!

[Democrito]

Joaquim,

I am learning and this topic is new to me (CORDIC). Regarding the interpolation, I understand that between two values, one is created in the middle (so to speak, it is to fill gaps). I was thinking about this idea a few days ago, but we found that between two imprecise values ​​(I mean not exact) that we want to fill in middle (simple weighting), what we will get will still be inexact, at least that's my logic. If we are looking for, say , three exact decimal places, we need that to be the numbers we expect, so at least in this case, I think the only solution is to increase the bits. I've been looking for a trick or something for several weeks, but for now I'm forced to solve this problem in the conventional way (CORDIC or tables).

Not having a "saving" solution now shouldn't be a problem. We are going to create modules that solve trigonometric problems and if we discover a cheaper solution over time, we will apply it!

I hope you have sweet and restful dreams!

[Jo mo]

Hola Democrito,

Do not worry, i am learning too. Specially the Cordic algorithms!

The idea with interpolation is to decrease the stair effect that we have with our table solution can see in the following picture (blue). that we will have with our simple table solution.

by having a first order linear interpolation we  can decrease the error.

About the precision, we can add 10,100,... points on every straight red section (between 2 values on our table).

To decrease the remaining error(difference between black and red), we can increase the order of interpolation 2th,3th (at the cost of more resources) but it may not be necessary, we have to stop somewhere :-)

But as you said, no hurry we can implement improvements with time, when we really need more precision!

Thanks again

Have a good evening and night too!

[Democrito]

Adjunto en este post dos ejemplos de senos y cosenos en Q1.10 y Q1.16. Los módulos, ejemplos y actualizaciones las estoy subiendo aquí.

Según he podido ver, vale la pena crear tablas, no consume tantos recursos como pensaba y es lo más rápido. Sobre esto no tengáis en cuenta el consumo de los ejemplos, porque ahí hay mucha carga de circuitos para traducir el formato binario a formato "humano" (a través del serial).

Los Q1.10 dan una resolución exacta de los 3 primeros decimales. Verás 4, pero al último no hay que hacer caso.

Los Q1.16 dan una resolución exacta en los 4 decimales que verás a través del serial.

No tengo nada que destacar que no haya comentado antes, pero sí hay una cosa nueva importante que vale la pena remarcar y es lo siguiente:

Cuando fui a hacer los ejemplos de seno y coseno en Q1.10 quise usar un módulo "traductor" que ya tenía hecho que pasa de Q16.16 al serial. Como son dos formatos distintos hay que hacer unos ajustes en los buses (y no es como de costumbre). La regla de oro es saber dónde está el punto. El punto es ficticio, pero mentalmente sabes que una parte es entera y la otra fraccionaria, entonces, para ajustar los buses de un formato y del otro se hace así:

El bit más bajo de la parte entera ha de estar a la izquierda de ese punto ficticio, y el bit más alto de la parte fraccionaria ha de estar a la derecha de dicho punto. Todo lo que no se use ha de ser llevado a 0.

En los ejemplos de seno y coseno en Q1.10 veréis un módulo que se encarga de hacer esto llamado "Q1.10 to Q16.16 bus adapter".

He usado el formato Q1.xx (en vez de Q16.xx) por economía de recursos y buses, ya que el valor entero sólo puede ser 0 ó 1 (el signo está a parte y lo tengo como un bit aislado).

Los próximos días voy a tratar de sacar un atan2() y seguramente será con el algoritmo CORDIC.

[Jo mo]

Hola Democrito,

Thanks for that one too !

i started playing around this same subject but i am much slower than you ;-)

i am trying to make a sine block with:

16 bit input signQ9.6  ( decimal range: -512.° to + 511.98°)

16 bit output signQ1.14  ( decimal range: --2  to 1.9999)

Then for testing it, i have to complete two converters:  

-ASCI to signQ9.6

-and  signQ1.14 to ASCI

for info: (if needed ) i am using Matlab to quickly make conversions:

- from decimal to signed Q x,y (function dec2q )

- from signed Q x,y  to  decimals (function q2dec )

i can give more details about that if needed !

i also made a little excel sheet to help quickly choose the best signed fixed point format ( Qx,y ) for the range and resolution that we expect for our datas ( in ou case: angles has input and sine results as outputs) !

Have a nice day

[Jo mo]

Hola Democrito,

 Reading at the wikipedia page    i have few comment about Q terminology.  Please correct me if i am wrong!

1-  Q x.y = signed fixed point  and     UQ x.y = unsigned fixed point

Here are your fixed point blocks +  one  of those present  in the iceArith collection

- Has the signals travelling in the (11bits and 32 bits) buses are all positives / unsigned, i think that the U is missing on all the blocks descriptions

- also in the block Sign Q16.16  to TX  the use of term sign Q16.16 is misleading.

 - Because the minus sign is not included in the bus. (when the sign is included in the bus, the negative numbers should even be a complement of two)

if you want to insert the sign in the bus you can than call your module sign "Q16.16 to TX"

But if you want to have a total 32bit bus maybe you can have 1bit for the sign,16bit for integers and 15 bits for fractional part" --->  "Q16.15 to TX"

This is what i did to convert the 16bit unsigned value coming from the sine lookup table to a Q1.14  (signed -2 to 1.999)

All this is tricky, i am becoming craisy with that Qx,y stuff :-)

But small details can induce misunderstanding errors when we connect all those block together!

Thanks and have a good evening

[Democrito]

Hi Joaquim,

I'm not an expert on "fixed points", I get it as I go and believe me when I say I know as much as you do.

My way of working is what's driving you crazy. You are right in everything you have told me and I will confirm it to you as I understand it:

About the sign: that's right, the output is always positive "UQn.n", however the sign is just a separate output pin. And you have solved it very well. If the sign pin is 0 (positive), do nothing; if it's 1 (negative) then do the 2's complement. You have to do the 2's complement of everything (integer and fraction part) as if it were a single block.

As I understand it, if you want for example a signed Q8.8, then you need one more bit for the sign and it would be like this:

sign (1 bit) + integer part (8 bits) + fractional part (8 bits), in total you need a 17-bit bus.

Your way of proceeding is correct, because you will be able to do direct arithmetic operations (taking into account that the point of the two numbers must coincide).

Integer and fractional division modules:  All the modules I've made that do splits (fractional or not), are all Uinteger (unsigned).

To divide a positive number and a negative number (and it only divides positive numbers) my logic tells me to proceed like this:

Different signs: (+ - , - +)
Take the 2's complement of the number that is negative, this will make it positive. The result must be negative, so you do the 2's complement of the result. 

Equal signs: (+ +, - -)

If both numbers are positive, you don't need to do anything.
If both numbers are negative, take the 2's complement of both. The result is positive, so you don't need to do anything here.

Always keep in mind that the sign bit is another bit that you add.

For example, if I have 8 bits as an integer, the sign is one bit plus, so it needs 9 bits.

Or, if you don't need to exceed 8 bits, then the highest bit is the sign bit. instead of a resolution of 255 .. -256 (9 bits) you get 127 .. -128 (8 bits). In both cases the sign bit is the highest.

Remember that when you do the 2's complement of a number with an integer part and a fractional part, it is done to the full bus, including the sign if it has one.

If there is something that I did not explain well or I have left some detail, do not hesitate to tell me.

Good evening.

[Democrito]

The reason I keep the sign bit separate is because it was the only way to keep a table of 91 elements. If I had added the negative numbers, it would have meant twice this size.

[Democrito]

Convert a decimal number to Qn.n:

[There is not yet a module that multiplies fractional numbers, this means that the computer must do the operation before sending it, that is, already converted to Qn.n. Surely there is some trick, but I don't know yet]

* Imagine that you want to convert the conventional number "3.14" to Q2.8
- With the "integer" you don't have to do anything. That 3 goes into the integer part.
- The fractional part is "0.14" and you multiply it by 256. That result is now the fractional part. You put that result (just the integer part, which in this case is 35, and if you round up it would be 36, it is a better result.) into the fractional part.

Another example:

* Imagine that you want to convert the conventional number "3.14" to Q2.10
- With the "integer" you don't have to do anything. That 3 goes into the integer part.
- The fractional part is "0.14" and you multiply it by 1024. That result is now the fractional part . You put that result (just the integer part, which in this case is 143) into the fractional part.

You are always going to multiply the fractional part by the power of 2 of the second number of Q:
Qx.8 then multiply by 256 the fractional part
Qx.10 then multiply by 1024 the fractional part
Qx.16 then multiply by 65536 the fractional part

If it was "-3.14" proceed the same way (as if it were positive) and when you have the integer and fractional part you do the 2's complement. Remember that you will need one more bit for the sign.

In this type of conversion resolution is always lost in the fractional part.

Convert Qn.n to decimal:

Example, if it is Q2.8 and we want to convert it to decimal. Let's say we have the number:
b011.0010 0100 ------> d03.36
We take the integer part and leave it as it is.
We take the fractional part and multiply it by 100 and, and then we divide by 256, the result is "14.something", we keep only the integer part of that result.
If the integer part is 3 and the fractional part is 14, we have 3.14!

Example, if it is Q2.10 and we want to convert it to decimal. Let's say we have the number:
b011.00 1000 1111 ------> d03.143
We take the integer part and leave it as it is.
We take the fractional part and multiply it by 1000 and, and then we divide by 1024, the result is "139.648" (almost 14!), we keep only the integer part of that result.
If the integer part is 3 and the fractional part is 139, we have 3.139! (almost 3.14!)

[Jo mo]

Thanks Democrito, for you explanations, i understood them very well !

Your way of working is very good, it produces results!

What make me crazy is trying to understand mathematics and "multiple conventions" with my "sclerosed brain" :-)

The only think i do not understood is (in your post two hours ago) the reason for not putting the sign in the bus! 

You can use the circuit i put in my last picture (with the compliment of two and the selector driven by the sign output of de "quadrant angles refactoring" code block) .

So no need to output a separate sign output from the sine block!

The number of element of the table is not important. Maybe more important is that every element should contain 16 bits ( eg: element 2  =  h' 025F ' ) to get some precision !

i just read your last post about conversion in bot way!

it is very clear !   a reference !!  thank you!

have a good evening !

[Democrito]

Good night Joaquin,

I'll take your advice and make all the modules for sine and cosine give the negative angles in 2's complement format because that's how they're really going to be used.

Since you already solved this procedure, I will take the liberty of doing it with time. And if there is any more problem, you tell me and I get down to work.

Friendly regards!

[Democrito]

Joaquim, where I say:

<<
[There is not yet a module that multiplies fractional numbers, this means that the computer must do the operation before sending it, that is, already converted to Qn.n. Surely there is some trick, but I don't know yet]
>>

Turns out there is a very simple solution and it was right under my nose. In a few days I will release a module that solves this problem.

[Jo mo]

Hola Democrito,

Not sure if we are speaking about the same but,

in my current modification of you sine-table design, i modified the "serial to binary16 module"

1- i modified the "enter key detection block" to also detect the coma key (and the minus key) and output them

2- i used this comma output to feed the line of shift registers! instead of feeding from the bottom, i am feeding it from the middle(coma position)!

here for 3 integer digits (from the middle to the top) and 2 fractional digits (from the middle to the bottom)

- then i added the ""2'compliment mod" at the ouput of that module "serial2bin" block (that can be renamed one day "serial xxx.xx 2 sigQ9.6" block)

Remark, i could not yet test it fully so it can be faulty/contain mistakes !

 if you want to try this "draft", you "can add as a block"-it to your design . here it is!

[Democrito]

This Sunday I will tell you something, what you have done looks very good!

[Democrito]

Hi Joaquim,

I have been taking a close look at your circuit (visually) and the logic you have used is correct, but there is one part of the circuit that I think is not correct.

That ASCII to Binary converter is for integers, I think that in this part of the circuit you have to separate the integer part from the fractional part. That is, the fractional part must have its own converter.

Also, after converting the fractional part, a treatment must be done. You are using a Q9.6 (nine bits for the integer part and 6 for the fractional part), so you need to multiply the fractional part by 2^6 (ie by 32). This must be done after passing the converter (and it must be a separate converter), then the conversion from conventional numbers to binary will be correct.

Everything else, i.e. the point and the possibility of doing the 2's complement seems correct.

I'm going to try to make a design with everything I've told you, I'm sure there will be more details to attend to...

[Jo mo]

Hola democrito,

You are right this ascii bloc is for integers.

in fact i am virtually multiplying the input number by 100 (to bring the two fractional digits in the integer domain).

So for exemple when the user think he is entering 1.23, in fact he is entering 123 which is after converted to binary at the output of the asci block!

As i understaind, the objective of the "fixed point" numbers is to deal at the end only with "virtual" integers in the logic/fpga domain !

Have a nice day!

[Jo mo]

hola Democrito,

thinking a bit more i understood that  i wrote bullshit in my last post i can not just multiply by power of tens it breaks the Qx.x system!

Only power of 2 are allowed!

I need to think a bit more ;-)

[Democrito]

Hi Joaquim,

I have been trying all day to transform an input from real numbers to a fixed point and I have not succeeded. I'm at a dead end (at least for now).

What I have achieved is to receive an input of fixed point numbers through the serial and translate it to binary. It's actually like receiving two whole parts. I solved this part as I told you in a previous post: Using two ASCII to binary converters. To test this part of the circuit, I used a dual binary to ASCII converter for the serial port.

It remains to be able to convert the fractional part into a real fractional part in binary. I prefer not to talk about how to proceed because I think it would confuse more than necessary.

Anyway I leave you the toy that I have created, although it does not serve our purpose.

A friendly greeting.

[Democrito]

In the end I have managed to make a circuit that may interest you and it works very well.

From now on, when I say "real" I mean the way we enter numbers into a calculator or by typing them into a serial port.

The circuit that I attached in this post manages to transform from "real" to Q16.8 with sign, although the output is from Q16.16 (later I will comment on this detail)

To keep in mind so that everything goes well:
Always write two numbers as a fractional part.
For example: "1.50", "4321.53", "-9999.99"

To keep in mind so that everything goes well:
If you write "1.5" it will interpret it as "1.05", you always have to write two figures, even if it ends in 0. In this example the correct thing is "1.50"

Never write more than 2 figures in the fractional part.

The maximum value in the integer part can range from -32768 to 32767.

This image is an example of how it looks.

Since it is Qx.8 format, we can only consider two numbers as a fractional part (yellow area). The rest of the numbers that follow are because in this demo I am using a 16-bit bus when it should actually be 8.

If you want I can adapt the circuit to your needs.

This is just a demo of how to make a real input and convert it to Qx.x

I attach the new circuit to this post.

Good night!

[Jo mo]

Hola Democrito,

Thanks for your hard work on the subject!
i tested you last circuit and as you wrote, it works great.

two remarks:
1 - it works in the range -32768 ---> +32767, ( so the 5 digit value 88888 will not work!)
this is (at least) because the size of the output bus for the integers of the ascii block is "only" 16bits.

2 - I also found it is using a lot of resources for "simple" numbers format conversions :

On the a Alhambra board build:  1676 LC  (around 22%)
On the a Colorligth board build:  1135 LUT + 9 multipliers(18x18)

I have the feeling that we may be trying to kill a mosquito with a 25 Kg concrete building block. :-)
One of the think that can eats quite a lot of resources is the multiplications/division by decimal number 10,100,1000... those are heavily used in the "ascii to binary" blocks.

     " assign    bin = (decm * 10000) + (unim * 1000) + (cen * 100) + (dec * 10) + uni;  "

As you know, to be resources efficient we should try as much as possible to multiply/divide only by the following decimals 2,4,8,16,32,64,128,256,... which are converted the fpga circuit as in simple bit shifts (left or right)

But, I do not want to make you loose all your time on this! Specially, if you have more interesting subjects to work on ;-)

So i will have a look on all of this, to see if optimisation is possible by myself !

And if needed i can reduce also by myself the size of the buses to fit better my application.
in any case i will share any findings here!

Once again thank a lot for all that time and neurons burned :-)

A big hug Democrito!

Joaquim

[Democrito]

Hi Joaquim!

1.)  1.) With the integer part there is no problem if you want to increase the bits, you increase the bits and that's it. With the fractional part it's different, you need a mathematical adaptation, and knowing if a certain bit resolution gives you the resolution you need or not.

2.) Optimizations always interest me because it means going one step beyond what has been learned.

I have been thinking for a long time that, for example, for very complex things or things that consume a lot of resources and speed is not critical, such as displaying information on a serial terminal, the solution would be to create a small microcontroller that would be programmed in machine code and would facilitate these tasks. . In other projects that I have presented in this forum, I presented a very simple little micro [I called it Atto] (less than 280 luts) that simplified certain tasks, such as sending and receiving data for I2C and SPI. In this sense, it would be a question of creating a specific one that could manage these conversions. The one I made lacks ALU and many other options and has nothing to do with orthodox micro design. (I did it without knowing anything about micro architectures, I just wanted it to execute instructions).

And I think that in a few months I will finish doing something like that, but first I want to finish some key projects and this trigonometry project is one of them.

I think it would be very convenient to create a small specific micro for conversion issues, the problem is that for many this would be a "black box", in addition to the fact that it requires a lot of documentation for few or none who want to learn how to program it.

Another big hug for you Joaquim.

[Jo mo]

Hola Democrito

I missed your "atto" micro, yes it can be a good idea to do the "slow" process  (related to a human interface) with a micro. specially if you can use the same micro for multiple actions (in our case: decimal--> Qm,n conversion, Qm,n --> decimal conversion, and maybe also for the serial in and out transmissions)

For now i will try to look carefully at the designs we worked on, to try to learn/aquire the feeling what verilog code eat resources, this is useful to get a good feeling about the limits of the fpga coding!
As hobbyist we can not yet afford 1 000 000 Luts fpgas (around 20'000$/chip)  :-)

About the arithmetic's for sine/cos and others functions too, do you think that it will be possible to define (as a starting point)
few specific fixed point format numbers that we ca then use for most of our arithmetic blocks.

eg:

 format 1:    signed Q10.5
    range: -1024,00 < x < 1023.97
    resolution: 0.03
    bus size 16 bits
    Advantages:We can use it for angles (but not only). and it is good for decimal/human interface (it correspond well to 3 decimal digits integer and two fractional digits )
    remark. if we use 2 more bits in fractional part (Q10.7) it will correspond even better to the 2 fractional decimal digits)
   
  format 2:   signed Q 1.10
    range: -2,000 < x < 1.999
    resolution: 0.001
    bus size 12 bits
    advantages: good for sine and cosine results range (-1,000 < x < 1.000)
   
   format 3: .....
   
Then for those formats we can make serial converter(in and out) for serial monitor debugging purposes (but not only)
   
Have an as great day as possible.

Joaquim

[Democrito]

Hola,

He conseguido hacer un atan2(y/x), en plan borrador. Como la mayoría sabréis, el atan2 lo que hace es sacar el ángulo de dos punto (x,y) de un plano (dicho en plan bruto).

El circuito que adjunto de ejemplo es este:

Funciona a través del serial. Damos dos coordenadas cartesianas (primero  el eje "Y" y después el "X") y nos devolverá el ángulo.

En esta imagen de arriba podemos ver ejemplos de cómo se introduce los datos y comprobar cómo sería la salida. Hay que recordar que el algoritmo CORDIC es un algoritmo de aproximación, en este caso, puede cometer un error de (+-) 0.01 dentro de un Qx.8, es decir, sólo nos fiamos de los dos primeros decimales. Otras cosas que podéis probar es por ejemplo cuando dos coordenadas son iguales (10,10), (234,234), (903,903) en estos casos siempre ha de dar 45º. Cuando se introduce 0-0 da como resultado "indefinido" (creo que se llama "NaN" [not a number]) y en la imagen podemos ver que pone "Error!" cuando sucede eso.

Usa de entrada un bus de 16 bits, pero en realidad sólo utiliza 10 bits, por tanto no se debe introducir números (siempre enteros) mayores de 1023. La salida es un Q10.8 dentro de un bus de 32 bits. Para evitar crear un traductor Q10.8 a decimal lo que hice fue reorganizar los buses a través de un adaptador y evitar así crear otro módulo específico

Me queda pulirlo un poco más, además de que he de mirar cómo meter números negativos y otros detalles. Considerar este ejemplo como un borrador funcional.

Una vez que quede todo bien, cogeré los otros módulos de senos y cosenos y muchas otras cosas que he ido haciendo por el camino (como los convertidores de Qx.x a decimal y viceversa) las organizaré y las subiré a iceArith.

Adjunto ICE de ejemplo.

Saludos.

Post Data: Si alguien quiere un ejemplo de este algoritmo (atan2) hecho con programación (y es totalmente digital, es decir, sólo usa sumas y desplazamientos) lo puede ver aquí: https://github.com/Democrito/Didactico/blob/main/CORDIC/BASIC/atan2_Qx_8.bas

[Jo mo]

Hola Democrito,

Thanks for this new Atan block!  it looks nice!

Your block for converting between two different Qm,n formats is a good idea ( and "resources cheap" idea )!
and you are right we may not need to have 100x Qm.n to serial converters.

Following your example, i played a bit with this  Qm,n stuff.
I made two converters:
- UART to Q10.7 and a Q10.7 to UART  this format is very well suited for 5 decimal digits (XXX.XX). see below

Few things i tried to optimise:
- Resources usage: now 673 LC on a Alhambra builds (vs 1676 LC for your version that has 2 more integer digits(that you called Q16.8))
- auto enter after two fractional decimal number where sent to the UART
- little ("probability based" correction) for the loose of precision due to the conversion from decimal to Q10.7 format. and same for Q10.7 to decimal!

- added a re_init input (The q10.7 input value is buffered until the receiver of that value, doesn't need it any-more ans sends a re-init signal.  Which will allow the reception of a new serial transmission!). In your previous version, the re-init was automatic(after few clock cycles).

Thanks and have a nice week guys!

[Democrito]

Congratulations Joaquin! I have tested it and it works very well!

And you have done so well that it consumes very few resources.

I was also working yesterday but for a Q16.16 and got it to work fine. I solved the problem of being forced to put all the decimals (example: if I typed "1.5" it would interpret it as "1.05") I have seen that you have also solved that problem.

I attach an example similar to yours. Although much heavier, a Q16.16 can be made into a smaller one by rearranging the buses.

I'll post the Atan2 block (the last one) later this week if all goes well. The important thing is that it can accept negative numbers to be able to deduce the quadrant in which it is located. I also plan to increase it to 16 bit with sign instead of 10 bit.

Thanks for your highly optimized block! When we finish this project we have to organize all these blocks.

Good evening!

[Jo mo]

Hola Democrito,

1) Next i planed to do the 2 converter blocks for Q4.14 (normal range-16 to +15.9999, resolution 0.00006). But we will be available to input serially only in range -9.9999 ->+ 9.9999
This block will be good to treat the sins (x) or cos (x) results (range +1..-1)
And if a maths block with Q4.14 output gives a value outside the range -9.9999 ->+ 9.9999  (eg: between+10.0000 and +15.9999) a  "OutOfRng"   message will be transmitted to the serial monitor!

2) Your Q16.16 (33 bits, as it is signed) is a good idea to cover a very large range (-65536.0000 .. +65535.9999)!  
We will have here 10 significant numbers in total (against the 5 significant numbers of my Q10.7 and Q4.14)!  If a quite high precision is needed in a large range of values!

But as the values from 65536.00000 to 99999.99999 that can be enter serially are out of Q16.16 range, maybe it is better to go to Q17.17

Q17.17 will give a  range of -131072.00000 to 131071.99999.
- But we will only allow to serially input from -99999.99999 to -99999.99999
- and for serial output, (as i will do for my Q4.14 block° we can send serially a message like "OutOfRng" when the fpga maths blocks outputs outside the +/- 99999.99999 range.

So in the end, we will cover the following ranges to do all the fixed-point signed mathematics!

And if (for resources optimisation questions) we use another Qm,n formats ( eg Q 9.8) in our designs. Than we can make (as you did in you atan2 ice file)  a  Qm1,n1 to Q m2,n2 (Q9.8. to Q16.16)

What do you think?

Than sure we can organise those block in a collection, maybe in the iceArithm one.

Something like this

Have a nice day!  Hug!

Joaquim

[Democrito]

Joaquím, Since last night I have been watching how you solved your circuit and I have been amazed.

For example: When numbers are entered through the serial port, I save them one by one and then convert them to binary (SerialASCII to Binary). Instead, you do magic by applying a formula: "outp<=outp*8+outp*2+in;". My mom! It works very well! Then, in the fractional part, apply another formula... Everything you have applied is to study it very closely because in addition to working well, it consumes very very few resources!

The more I look at your circuit, the more stumped I get. I think that very few people will be able to value this, at least I did not know it, and as I said before, your solution is worthy of study. I am very slow in my thinking and it will take me time, but I see pure gold in your way of solving. I am going to keep your circuit as something very valuable and I will learn a lot.

Don't worry about what you say in your post, that's where you rule. I want to finish atan2, and when I'm done, if I can help you with the Qn.n conversions, let me know and we'll create all the necessary modules, but I still have a lot to learn about its efficiency (pure magic).

My idea is to just create one with the maximum number of bits and then branch it with buses, but if you think it's better to do that specifically, we'll do that.

Thank you very much for your work, Joaquim, I am amazed. A hug!

[Jo mo]

Hola Democrito,

Thanks for your kind comments!

It is not Black magic, ;-)  it is just that i am not good enough at explaining/summarize what i do !

For the formula :     outp<=outp*8+outp*2 + in;
We loop 3 time ( max ) trough this formula to enter the max 3 integer digits one by one ( before the coma)
This loop replaces the formula:   bin =  (cen * 100) + (dec * 10) + uni;   of the ascii to bin module(simplified)
 
As you see, i replaced outp*10 by outp*8+outp*2  because it seams the compiler eats less resources with the second version.
 It the later case, it sees 2 simple bit-shifts ans one addition.  
with that trick, on my colorligth board i spare 1 dsp multiplier and on Alhambra board, it uses also less LC.

This trick can only be used when we multiply a variable(here outp) with some special simple constants like (10,100,1000,...) that can be compose by sums of powers of two.(eg: 10= 8+2 = 2^3+2)

For example, In your atan2 ice file, you can (gain around 70LC) by changing the q16.16 block.
At the output of that block, you can change the code  


to:

 // Convert the decimals part to a notation that can be represented.
//wire [27:0] temp;

reg [27:0] temp;
reg [3:0] cpt=0;

always @(in) begin
     temp<=in;
        for(cpt=0;cpt<=3; cpt=cpt+1) begin  
            temp<=temp*8+temp*2;                 // = temp*10  and it is hardware reproduced (in cascade) 4 time to get temp*10000.
            cpt<=cpt+1;
        end
end

assign out = temp >> 16;


It is fine to have one converter with the maximum bits. But when only few bits are needed for a certain variable, the compiler may not be able to simplify the circuit enough and it can consume a lot of resources!

Sorry but i am a bit obsessed with resources usage! :-).

I want us to be able to fit as much complex functions as possible in our small entry level fpgas!

Who know, one day, i may be able to fit a music synthesiser (with plenty DSP calculations) in my colorligtht i5 board!

But do not worry about that, do your amazing and inspiring blocks as you used to do!  And, if i want to, i can bring resources optimisations myself !

Thanks a lot for your work too Democrito and have a good night!

[Jo mo]

Hola guys,

Hope you enjoyed a nice Easter meal today ,as i did !   (even if i am a quite bad Christian) ;-p !

Following is a "niche interest" stuff, for those which where not disgusted at school by their maths classes!

So has "promise" few week ago here his a new Qm,n converter couple (serial to Q , Q to serial)!
Starting from Democrito's designs, After the Q10.7 few weeks ago,  i made these days the Q4.14  (Fpga resources used around 950LC on alhambra) see joined files !

i am also joining a rework (v2) of my  Q10.7 (removing the feedback line that i added and which is not really necessary, (so it is in this aspect back to the original Democrito design) )

Next, week, i will be testing Carlos an Juan " fresh and juicy Wips " :-) trying to modify one of the Sine block made by Democrito (the Cordic or the table based one, not sure yet). Maybe with some interpolation circuit!

The objective will be to have:
-  a Q10.7 input (+/-360.00 degrees ) (no radians for now, but the conversion to that unit will be possible if needed later using efficiently a Q4.14 input! (+/- 2*Pi ))
-  a Q4.14 output ( +/- 1.0000 )
-  and have enough precision to use all those available digits.

 @ Democrito : Thanks again to have launched this great Math thread/subject, i learned a lot playing with verilog code;-)

 @ urbi et orbi :  Enjoy your "free of work" Monday if you have one ;-)!

[Democrito]

Thank you Joaquim,

Just to comment that surely (I don't know, but I think it will be possible, time will tell) we will also have trigonometry in radians. The "atan" tables (in CORDIC algorithm), instead of degrees, should be replaced by radians. I still have to finish solving Atan2 (what I put in is only valid for 90 degrees) and I have my eye on an arc cosine for which I haven't found an electronic solution yet, but if it was, it might mean a solution. to solve the kinematics. With these functions, articulated robot problems could be solved (my interest is robotics).

I've seen your circuits and it still amazes me how you solve problems that aren't obvious. I like the way you think when you solve.

A hug!

[Jo mo]

Hola Democrito,

Thanks a lot for your comments!

They gave me the idea of making a degree to radian converter !  see joined file!

The resources used for  converter block alone should be around 300LC (for the block alone, without the two serial-converters) but it requires 16 clock cycles to make the multiplication.  doing it in around one clock cycle cost 700LC for the block

Remark: the inverse function "radian to degree" that may be interesting for outputting the result of arcsin, arcos, arctan function should be very easy to do (  /0.0157 instead of * 0.0157...) (just left shifts instead of right shifts)

So i will try to evaluate what is the better choice for the input units of the sine,cos function! 

But, if some of you have a clear(degrees or radian) preference, let us know your thoughts!

big hug!

[Democrito]

Wow! Joaquim!

Marvelous! I honestly can't follow you, you are way ahead of me on this project. Anyway, I'll try to approach this problem in another way (just try it, I don't know if I'll achieve anything). In any case, the path you have opened is the one that best paints it.

My sincerest congratulations!

A hug!

[Jo mo]

Hola Democrito,

I am sorry to share stuff without much explanation !Documentation takes time, and i am not good at it for sure ! ;-)  Life is to short!

The drawback is that even myself when i come back to thinks, i did, i have to rethink sometime quite a lot to understand it :-))

I am not an organised person, if you see my working space you will understand :-)

In my brain i have the same dirty mess, but sometimes, hopefully, comes out some mysterious/unexplained stuff that can have some application/use !

Anyway to really understand and start working on those technical subjects, we have to really get into it personally! And as we are all distinct people, (with different brains), we just take different routes!

We also have different objectives!

Mines here are:

-  to experiment and learn "complex" hardware design and verilog code!

- And in a very long therm use these experience to make complex blocks to be used in " music creation field", FFT,...

So just go your route and share with us when you want! ( As you already did).

Hopefully, has it did for me, your work will inspire plenty of other young and old people ;-)

On my side, i will play a bit with the sine now. And after that i have to convince myself to put on hold those math " stuffs", because i absolutely need to focus on a project that i have started more then 10 years ago and which is important for me!

That project as an Fpga, a teensy microcontroller and other stuff in it, so i hope all i am finding in that thread will also be of some use one day ;-)!

Thanks a lot for everithynk and have a great day.

[Democrito]

Joaquim, (Surely you already know this project)

The next thing I tell you is not about FPGA, at least not necessarily. But since the sound intervenes.

A few years ago I saw a project that really impressed me. Images appear on the oscilloscope (psychedelic type) and at the same time it creates music (techno type).

As an introduction I put this video: https://www.youtube.com/watch?v=4gibcRfp4zA

Audio files to create these demos (they are examples) : https://drive.google.com/drive/folders/1UHvGC6-TDywFri7am8YJl5G6svK33qhC

Software to create images and songs (Some are paid and others are open source) : https://oscilloscopemusic.com/software.php

The ideal is to do it with analog oscilloscopes, digital ones have many options to make it look good. It can also be done with a television where you control the dot, by putting amplifiers on the coils that control the beam in a cathode ray tube.

Greetings!

[charli va]

Democrito this is very interesting!

--
Has recibido este mensaje porque estás suscrito al grupo "FPGAwars: explorando el lado libre" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a fpga-wars-explorando-el...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/fpga-wars-explorando-el-lado-libre/cce6e8bb-ef63-4cb3-9c27-76491e14c9afn%40googlegroups.com.

[Democrito]

Carlos, there may be students who resist the oscilloscope, and this is a way of wanting to have total control over it, and whose enthusiasm is very important!

I leave a playlist as an example: 

https://www.youtube.com/watch?v=Y04LBDTsGIk&list=PLc4EnsriUcfQPomSF3Eh6sB143HE2r0tf&index=13

By the way Carlos, taking advantage of this "off topic", with this video that is for you, since you know about Artificial Intelligence, it is about analog computers, and they are going to be integrated into digital ones (add the best of both worlds), especially for the AI:

Español latino: https://www.youtube.com/watch?v=qNtxODk_Lmk

Ingles: https://www.youtube.com/watch?v=GVsUOuSjvcg

[Jo mo]

No, i didn't heard before, about that "oscilloscope music" trend !

Some people are just crazy :-) it is funny!

i have no more cathodic screen around me! Maybe this can be done using some lazer projectors !

 i just found that!  https://www.youtube.com/watch?v=GyTGXrL5Vas

[Democrito]

Hola,

El anterior Atan2 que publiqué sólo servía para entradas positivas, dando resultados de ángulos de 0º hasta 90º. Ahora he conseguido los 360º.

Dado un punto (x,y) atan2 nos devolverá el ángulo, como puedes ver en la imagen. Un arco-tangente convencional sólo puede resolver el ángulo para los cuadrantes 1 y 4. Sin embargo un atan2 nos lo resuelve para los 4 cuadrantes existentes. Esta función trigonométrica es muy útil en la cinemática inversa de robots articulados.

Las entradas X e Y son de 16 bits con signo, esto significa que podremos introducir puntos con resolución desde -32768 hasta 32767. La salida del ángulo está en formato Q9.8.

Adjunto a este post un ejemplo para quien esté interesado/a en probarlo. Se introduce primero la coordenada Y y después la X (esto es así porque en realidad es Y/X) y a ese resultado se le hace el arco-tangente. En el terminal serie aparecerán datos como estos:

Los signos de los ejes X e Y son los que dictan en qué parte del cuadrante se encuentra.

Recordemos que todos los algoritmos CORDIC son de aproximación. Tiene una resolución de dos decimales que en la gran mayoría de los casos es más que suficiente (imagina un sólo grado dividido en 100 partes...). Los ángulos en este circuito nos da una resolución desde 0.00º hasta 359.99º. Los Atan2 convencionales dan el resultado de 0º hasta 180º, y de 0º hasta -180º, sin embargo he preferido la modalidad de 0º hasta 360º.

Si subes el circuito verás que ocupa muchos LUTs, pero esto es debido a los conversores que pasan de formato "humano" a máquina y vice-versa. Para no atrasar más este proyecto no he optimizado esas partes, requieren mucho tiempo y lo haré más adelante.

De momento doy por finalizada la trigonometría de senos, cosenos y arco-tangente. Lo siguiente que tengo pensado hacer es un algoritmo que nos haga la inversa de cualquier número (1/n), pero esto lo publicaré aparte porque no es trigonometría.

Saludos!

[Jo mo]

Hola Democrito,

i just tested you new arctan2 and it works really well !

For the resources usages, yes it is quite high!

Now on my board, it uses (2137 lut and 8 multipliers). your previous version of atan2 was using ( 1130 lut and 5 multipliers )

But on mi side i will put on hold the resources optimisation works, for now!  Not enough time !

And these week, i got a new FPGA board the "colorligth i9" with twice the resources of the colorligth i5 board !

I will launch later today a new discussion showing my first "blinky led" test of this board with icestudio !

Thanks again for all this amazing maths blocks!  i will test now the 1/n one !

Have a great Sunday !