Jump to content
 

N9WXU

Member
  • Content Count

    106
  • Joined

  • Last visited

  • Days Won

    37

Everything posted by N9WXU

  1. Assembly language may no longer be the mainstream way to write code for embedded systems, however it is the best way to learn how a specific CPU works without actually building one. Assembly language is simply the raw instruction set of a specific CPU broken into easy to remember pneumonics with a very basic syntax. This enables you full control of everything the CPU does without any translation provided by a compiler. Sometimes this is the only reasonable way to do something that cannot be represented by a higher level language. Here is an example from a project I was working on today. Today I wanted to create a 128-bit integer (16 bytes). That means I will need to add, subtract, multiply, etc. on my new 128-bit datatype. I was writing for a 32-bit CPU so this would require 4 32-bit values concatenated together to form the 128-bit value. If we consider the trivial problem of adding two of these numbers together, lets consider the following imaginary code. int128_t foo = 432123421234; int128_t bar = 9873827438282; int128_t sum = foo + bar; But my 32-bit CPU does not understand int128_t so I must fake it. How about this idea. int32_t foo[] = {0x00112233, 0x44556677, 0x8899AABB, 0xCCDDEEFF}; int32_t bar[] = {0xFFEEDDCC, 0xBBAA9988, 0x77665544, 0x33221100}; int32_t sum[4]; sum[0] = foo[0] + bar[0]; sum[1] = foo[1] + bar[1]; sum[2] = foo[2] + bar[2]; sum[3] = foo[3] + bar[3]; But back in grade school I learned about the 10's place and how I needed to carry a 1 when the sum of the one's place exceeded 10. It seems that it is possible that FOO[0] + BAR[0] could exceed the maximum value that can be stored in an int32_t so there will be a carry from that add. How do I add carry into the next digit? In C I would need to rely upon some math tricks to determine if there was a carry. But the hardware already has a carry flag and there are instructions to use it. We could easily incorporate some assembly language and do this function in the most efficient way possible. So enough rambling. Let us see some code. First, we need to configure MPLAB to create an ASM project. Create a project in the normal way, but when you get to select a compiler you will select MPASM. Now you are ready to get the basic source file up and running. Here is a template to cut/paste. #include "p16f18446.inc" ; CONFIG1 ; __config 0xFFFF __CONFIG _CONFIG1, _FEXTOSC_ECH & _RSTOSC_EXT1X & _CLKOUTEN_OFF & _CSWEN_ON & _FCMEN_ON ; CONFIG2 ; __config 0xFFFF __CONFIG _CONFIG2, _MCLRE_ON & _PWRTS_OFF & _LPBOREN_OFF & _BOREN_ON & _BORV_LO & _ZCD_OFF & _PPS1WAY_ON & _STVREN_ON ; CONFIG3 ; __config 0xFF9F __CONFIG _CONFIG3, _WDTCPS_WDTCPS_31 & _WDTE_OFF & _WDTCWS_WDTCWS_7 & _WDTCCS_SC ; CONFIG4 ; __config 0xFFFF __CONFIG _CONFIG4, _BBSIZE_BB512 & _BBEN_OFF & _SAFEN_OFF & _WRTAPP_OFF & _WRTB_OFF & _WRTC_OFF & _WRTD_OFF & _WRTSAF_OFF & _LVP_ON ; CONFIG5 ; __config 0xFFFF __CONFIG _CONFIG5, _CP_OFF ; GPR_VAR UDATA Variable RES 1 SHR_VAR UDATA_SHR Variable2 RES 1 ;******************************************************************************* ; Reset Vector ;******************************************************************************* RES_VECT CODE 0x0000 ; processor reset vector pagesel START ; the location of START could go beyond 2k GOTO START ; go to beginning of program ISR CODE 0x0004 ; interrupt vector location ; add Interrupt code here RETFIE ;******************************************************************************* ; MAIN PROGRAM ;******************************************************************************* MAIN_PROG CODE ; let linker place main program START ; initialize the CPU LOOP ; do the work GOTO LOOP END The first thing you will notice is the formatting is very different than C. In assembly language programs the first column in your file is for a label, the second column is for instructions and the third column is for the parameters for the instructions. In this code RES_VECT, ISR, MAIN_PROG, START and LOOP are all labels. In fact, Variable and Variable2 are also simply labels. The keyword CODE tells the compiler to place code at the address following the keyword. So the RES_VECT (reset vector) is at address zero. We informed the compiler to place the instructions pagesel and GOTO at address 0. Now when the CPU comes out of reset it will be at the reset vector (address 0) and start executing these instructions. Pagesel is a macro that creates a MOVLP instruction with the bits <15:11> of the address of START. Goto is a CPU instruction for an unconditional branch that will direct the program to the address provided. The original PIC16 had 35 instructions plus another 50 or so special keywords for the assembler. The PIC16F1xxx family (like the PIC16F18446) raises that number to about 49 instructions. You can find the instructions in the instruction set portion of the data sheet documented like this: The documentation shows the syntax, the valid range of each operand, the status bits that are affected and the work performed by the instruction. In order to make full use of this information, you need one more piece of information. That is the Programmers Model. Even C has a programmers model but it does not always match the underlying CPU. In ASM programming the programmers model is even more critical. You can also find this information in the data sheet. In the case of the PIC16F18446 it can be found in chapter 7 labeled Memory Organization. This chapter is required reading for any aspiring ASM programmers. Before I wrap up we shall modify the program template above to have a real program. START banksel TRISA clrf TRISA banksel LATA loop bsf LATA,2 nop bcf LATA,2 GOTO loop ; loop forever END This program changes to the memory bank that contains TRISA and clears TRISA making all of PORT A an output. Next is changes to the memory bank that contains the LATCH register for PORT A and enters the loop. BSF is the pneumonic for Bit Set File and it allows us to set bit 2 of the LATA register. NOP is for No OPeration and just lets the bit set settle. BCF is for Bit Clear File and allows us to clear bit 2 and finally we have a branch to loop to do this all over again. Because this is in assembly we can easily count up the instruction cycles for each instruction and determine how fast this will run. Here is the neat thing about PIC's. EVERY instruction that does not branch takes 1 instruction cycle (4 clock cycles) to execute. So this loop is 5 cycles long. We can easily add instructions if we need to produce EXACTLY a specific waveform. I hope this has provided some basic getting started information for assembly language programming. It can be rewarding and will definitely provide a deeper understanding on how these machines work. Good Luck
  2. Standby for a introduction to embedded... the ASM version. But suffice to say, the PIC assembler (MPASM) does understand #define for creating macro's just like in C. Setting breakpoints works the same way as in C but it is a bit more clear because you can set the breakpoint on exactly the instruction you want to stop at. The biggest hassle with ASM programming is the lack of any kind of support anything not supported by the ISA.
  3. Fantastic. I "unfortunately" remember those olden days of writing DLL's for use in Windows 3.1. One of my first JAVA experiences was writing a DLL to call a JAVA program to access hardware for an embedded system. There is a long list of things that don't "quite" work the same in C++ and C, never mind the differences between the different revision.
  4. Here is the advanced course version in assembly language bank0 udata delayLow res 1 delayHigh res 1 RES_VECT CODE 0x0000 ; processor reset vector GOTO START ; go to beginning of program MAIN_PROG CODE ; let linker place main program #define delayValue 10000 go_slow banksel delayLow movlw low delayValue movwf delayLow movlw high delayValue movwf delayHigh slow_loop decfsz delayLow goto slow_loop decfsz delayHigh goto slow_loop return START BANKSEL TRISA CLRF TRISA loop BANKSEL PORTA BSF PORTA,2 call go_slow BANKSEL PORTA BCF PORTA,2 call go_slow GOTO loop END It works exactly the same way as the C version.
  5. The defaults worked just fine! Of course there may have been a watchdog timer occurring someplace.
  6. Time for part 2! Last time, I gave you the homework of downloading and installing MPLAB and finding a Curiosity Nano DM164144 . Once you have done your homework, it is time for STEP 3, get that first project running. Normally my advice would be to breakout Mplab Code Configurator and get the initialization code up and running, but I did not assign that for homework! So we will go old school and code straight to the metal. Fortunately, our first task is to blink an LED. Step 1: Find the pin with the LED. A quick check of the schematic finds this section on page 3. This section reveals that the LED is attached to PORT A bit 2. With the knowledge of the LED location, we can get to work at blinking the LED. The first step is to configure the LED pin as an output. This is done by clearing bits in the TRIS register. I will cheat and simply clear ALL the bits in this register. Next we go into a loop and repeatedly set and clear the the PORT A bit 2. #include <xc.h> void main(void) { TRISA = 0; while(1) { PORTA = 0; PORTA = 0x04; } return; } Let us put this together with MPLAB and get it into the device. First we will make a new project: Second, we will create our first source file by selecting New File and then follow the Microchip Embedded -> XC8 Compiler -> main.c give your file a name (I chose main.c) And you are ready to enter the program above. And this is what it looks like typed into MPLAB. But does it work? Plug in your shiny demo board and press this button: And Voila!, the LED is lit... but wait, my code should turn the LED ON and OFF... Why is my LED simply on? To answer that question I will break out my trusty logic analyzer. That is my Saleae Logic Pro 16. This device can quickly measure the voltage on the pins and draw a picture of what is happening. One nice feature of this device is it can show both a simple digital view of the voltage and an analog view. So here are the two views at the same time. Note the LED is on for 3.02µs (microseconds for all of you 7'th graders). That is 0.00000302 seconds. The LED is off for nearly 2µs. That means the LED is blinking at 201.3kHz. (201 thousand times per second). That might explain why I can't see it. We need to add a big delay to our program and slow it down so humans can see it. One way would be to make a big loop and just do nothing for a few thousand instructions. Let us make a function that can do that. Here is the new program. #include <xc.h> void go_slow(void) { for(int x=0;x<10000;x++) { NOP(); } } void main(void) { TRISA = 0; while(1) { PORTA = 0; go_slow(); PORTA = 0x04; go_slow(); } return; } Note the new function go_slow(). This simply executes a NOP (No Operation) 10,000 times. I called this function after turning the LED OFF and again after turning the LED ON. The LED is now blinking at a nice rate. If we attach the saleae to it, we can measure the new blink. Now is is going at 2.797 times per second. By adjusting the loop from 10,000 to some other value, we could make the blink anything we want. To help you make fast progress, please notice the complete project Step_3.zip attached to this post. Next time we will be exploring the button on this circuit board. For your homework, see if you can make your LED blink useful patterns like morse code. Good Luck Step_3.zip
  7. It seems that in 2.15 they changed how the command line options are interpreted. in 2.10, there was a -fgnu89-inline option that ensured the inlines operated in a particular way (the GNU89 way). In 2.15 it seems this option is being quietly ignored. You can test by removing the option from the command line when you build in 2.10 and then you should see the same error.
  8. I have often been asked "how do I get started" in embedded software. As I think about this question, I realize that the basic steps to get started with embedded software are nearly identical to the basic steps required to bring up a new MCU or new hardware. There is always a bootstrapping process and a logic progression of steps before you are "home-free" and building your product. So here is my bootstrapping process, but broken down into each step so the process is clear for those just starting out. Step 1 - Collect the tools. The tools of the trade for embedded engineering are quite simple. Development environment. Hardware to develop on. Measurement tools to check signals. Programming tool (sometimes built into a development kit) Serial Monitoring tool (sometimes built into a development kit) an LED (usually built into a development kit) Step 2 - Install the development environment This process can be quite simple, like installing MPLAB IDE, or it can be quite involved, like installing the ESP-IDF environment for the ESP32. You will be living in this environment for the duration of your project so get it right. Step 3 - That First Project. This first project is THE MOST IMPORTANT ONE. If it goes well, you are off to the races, but if it goes poorly, you will likely regret your choice of MCU and start hunting for a different one. The first project is to blink an LED. The actual code is trivial, but this project will ensure the entire development workflow is working and you can program your target. Step 4 - Building Out This is where you start exploring your new world. What are the peripherals? How do they work? What kinds of things do folks do with these peripherals? Step 5 - Techniques of the experts Now you probably know enough to bull your way to success. I have seen some amazing projects built by folks who simply did not know how to quit. But, it would sure be nice if you could stand on the shoulders of giants and make your program easy and effective. Back in university one of my professors told a story of his first program. He was a physicist and needed to run a simulation. The idea was to write a program for the departments new computer to perform the simulation. Like many simulation, this one involved a newtonian solver for some of the math. This sort of solver converges on the correct answer iteratively. So he started his work. After a few days, he was bugging his computer science friend on the syntax of fortran and how to declare variables. Eventually, he had it doing one pass through math. Finally, he figured he knew his tool chain (fortran) and plowed ahead. A week later he proudly showed off his new program to his friend. His CS friend was impressed that this new programmer has produced such a complex application and it was working. His friend asked to see the program and was shocked at the 1 meter high printout. Scanning through the printout, he quickly discovered that while the physicist had figured out how to setup the math, he never figured out how to write a loop. The entire program was the same set of functions RETYPED (he did not figure out cut/paste) hundreds of times until the math had run enough times to converge on the result. Brute force does work....but there is usually a better way. Enough talking. It is time to get started. If you want to follow along, download and install MPLAB IDE from www.microchip.com/mplab and find a Curiosity Nano Evaluation Kit DM164144 (https://new.microchipdirect.com/product/search/all/DM164144). Next time, we will install the IDE, setup MCC and start that all-important LED blink. Good Luck.
  9. Embedded applications are hard for a large number of reasons, but one of the main issues is memory. Today I want to talk about how our C variables get initialized and a few assumptions we make as we use C to write embedded software. Let us take a few simple declarations such as we might make every day. char *string1 = "string1"; const char *string2 = "string2"; char const *string3 = "string3"; char * const string4 = "string4"; char const * const string5 = "string5"; In C99 these will all compile just fine but they are very different. In C++11, 2 of these will have a warning. We shall discuss them in order. Duration & Scope The first thing to notice is these variables are all declared outside of a function. That affects them in the following ways: External Linkage - i.e. they are global. Static Storage Duration - i.e. they are always active. allocated and initialized before control goes to main() Of course, if the keyword static had be placed before one of the declarations, the external linkage would have changed to internal linkage, preventing the variable from being accessed outside the compilation unit. Because they have static storage class, they will be initialized. If no initializer is specified they will be initialized to 0 or NULL. In each case, these have an initializer. So what is being initialized? Each variable is some type of a character pointer. So the value being stored in the variable will be an address. The address will be the address of a string of characters. The image on the right shows a data segment with the initialized variables. C does not actually specify where these const char strings need to be located. In GCC, they will be placed in the data segment and the variable will get the address of the string. However, in XC8, they will be placed in the Text segment (in FLASH). In the Arduino (GCC) environment you can force a string into FLASH by adding PROGMEM or using the F (FLASH) macro like this : F("String"). If the string is NOT in flash memory, then CINIT will copy the string from the text segment into the data segment. Then the variables will be initialized with pointers to the strings. String 1 The declaration for string 1 is simply a char *. This is a pointer to character(s). It is permissible for this pointer to be changed at run-time. i.e. the following is legal: string1 = string2; Of course, you will get a warning because string2 is a const char *. It is also permissible to do this: string1[3] = 'a'; Which will change the original string into "strang1". However it is NOT permissible to do the following: string1 = string2; string1[3] = 'a'; If you DO do this, it is likely to compile but there could be a few problems because string2 is declared as a const string so it must not be modified. Here is my compiler reluctantly obeying me and then the program crashes on the write. Just imagine that the string is in FLASH so writing is impossible without specific write sequences which the compiler probably does not know. In some environments you can get away with this. For example, I was using a Cypress WiFi device that loads the entire FLASH into RAM and then executes it. This code will run and it will not crash. Be very careful in such circumstances because in a few years you will be tasked to port the program to something else and life will be made hard because you did not fix the warnings. It turns out that in section 6.7.3 paragraph 5 of the C99 standard the behavior of line 22 is undefined. Your environment can choose to do anything it wants. String 2 & 3 The declaration for string 2 is a const char * and string 3 is char const *. These are IDENTICAL. This is in section 6.7.3 paragraph 9 "the order of type qualifiers within a list of specifiers or qualifiers does not affect the specified type". So these are pointers to a constant character(s). In a nice compiler, these characters would be stored in FLASH memory and never copied into RAM. That would be most memory efficient. However, GCC will copy these from FLASH into RAM and then use the address of these strings to initialize the variables. String 4 This declaration is to a const pointer. That is, the pointer value cannot change but the data pointed to by the pointer CAN change. Note the ERROR on line 22. Line 21 is perfectly fine. The data pointed by the pointer is NOT const so it is allowed to change. In C++11, the original declaration will have a warning because a char * is being initialized to point to a const char *. Never mind that the pointer is const. String 5 This is a combination of both sorts of constants. A const pointer pointing at a const character(s). This can be initialized from a const string just fine. But you will not be allowed to change the pointer or the data pointed to. Both line 21 and line 22 have errors and not simply warnings. We will do more of these variable initializer posts. The language rules are very clear but there are a few constructions that we don't see very often. And even worse, the assumptions we make about the syntax work often enough that we end up with some very strange notions on what the language allows. A good resource for testing your knowledge about strange C declarations is this website: https://www.cdecl.org Good Luck
  10. Good job tracking this down folks. It sounds like the templates need a little help for the 8-bit case and probably for the 32-bit case (running this on a PIC32). Is there any news on getting the templates on a public repository (GITHUB) so we can contribute fixes and help out?
  11. N9WXU

    Hello

    War stories seem to be one of the best ways for engineers to learn. Let us share and avoid repeating bad experiences.
  12. I have found the textbook “introduction to algorithms” by Thomas Cormen et al to be very helpful.
  13. Today we are going to explore the weird and wonderful trie (try). We are actually going to brute force a trie and we will write a basic code generator to synthesize a static trie so it our trusty NMEA token tester can stay in flash memory and fit in the PICmcu. I promise this is going to be the LEAST memory efficient trie you ever will see, but it is quick and it is easy to understand so let us press on. First things first, what is a trie? Simply, the trie takes the if-else construct we did in pt 2 and turns it into a data structure. I love this concept because it means I can write the trie parser once and simply be feeding it different data sets, it can process any language. In fact, I try to make most of my programs data driven so the code can be well tested and the data can be focus of our attention. Our basic trie will be implemented as a 2D array 26 x N. N will be adjusted to be as small as possible. The 26 comes from the 26 unique characters that can make up my NMEA string set. We will ignore lower case to make this dataset as small as possible. Here is a picture showing what we plan to do. In the picture we are finding the NMEA string "GPGGA". Each row of our 2D array represents each letter. If a letter is not involved at that layer of lookup, we will fill it with a -1. Each time we match, we learn the row where the next match is. By matching to the row, GPGGA and GNGSA both share the first G by pointing to the second row. On the second row, The P and the N will point further into the structures. Here is the search code: int trie_search(const char *s,int length) { int t=0; int p; for(int i=0;i<length;i++) { p = s[i] - 'A'; if((t = trie[t][p].index)==-1) return -1; } return trie[t][p].key_index - 1; // -1 hold over from a previous version. Generator can post increment the key } This looks fantastic. Only one table lookup per letter so this should be blindly fast. Let us take a look at the data. STRNCMP IF-ELSE RAGEL -G2 Hash Search (Hash/Search) Hash GPERF Hash GPERF no compare Trie Search GNGSA 399 121 280 326 167/159 374 126 915 GPGSV 585 123 304 288 167/121 374 126 871 GLGSV 724 59 225 503 167/336 113 113 1395 GPRMC 899 83 299 536 167/369 374 126 984 GPGGA 283 113 298 440 167/273 374 126 821 Well Heck! that is certainly not what we expected to see. What is going on? At the core, this algorithm is wonderful because it only touches each letter once. This is very similar to the IF-ELSe so I would expect that this algorithm would be very similar to the IF-ELSE. We need to dig a bit deeper. As I look at the code, the only thing that stands out is the actual table lookup. We have a 2D table of structs, with each struct being 2 bytes. I wonder if this function is using a multiply to compute the table address. 9840 l1579: 9841 031A ;example5.c: 65: if((t = trie[t][p].index)==-1) 9842 movf (trie_search@p+1),w 9843 031A 082C movwf (??_trie_search+0)+0+1 9844 031B 00A1 movf (trie_search@p),w 9845 031C 082B movwf (??_trie_search+0)+0 9846 031D 00A0 lslf (??_trie_search+0)+0,f 9847 031E 35A0 rlf (??_trie_search+0)+1,f 9848 031F 0DA1 lslf (??_trie_search+0)+0,f 9849 0320 35A0 rlf (??_trie_search+0)+1,f 9850 0321 0DA1 movf (trie_search@t+1),w 9851 0322 082E movwf (___wmul@multiplier+1) 9852 0323 00F1 movf (trie_search@t),w 9853 0324 082D movwf (___wmul@multiplier) 9854 0325 00F0 movlw 068h 9855 0326 3068 movwf (___wmul@multiplicand) 9856 0327 00F2 movlw 0 9857 0328 3000 movwf ((___wmul@multiplicand))+1 9858 0329 00F3 fcall ___wmul Here is the list file of line 65 and sure enough, there it is. Lots of code to setup the multiply and then a brutal software multiply. We were doomed. This simple brute force approach needs to be a bit more elegance in its data structures. I will include the packaged project and the generator and you can duplicate the work. I still like this concept, I challenge the readers to run some experiments and post the fastest/smallest version they can devise. Good Luck example5.zip trie_builder.c trie_builder.h
  14. N9WXU

    Melbourne Weather

    Wow.. I have been working on a rain gauge and trying to "bracket" the max & min rain a gauge might see. This is to ensure the data structures and RF packets are all suitable. So far my peak is is Mawsynram, India at 11.8 meters in a year. Tucson is pretty easy at 300mm
  15. N9WXU

    Melbourne Weather

    We are expecting rain and -1C tonight in Tucson. I expect snow on the mountains.
  16. N9WXU

    Melbourne Weather

    That is a cool feature. The weather here in Tucson is party cloudy and 11C.
  17. This week we will discuss a different strategy for tokenizing our words. This strategy will be to convert our word to a number in an unambiguous manner. Then we can simply see if our number is one we recognize. How hard can that be? The process of converting something into an unambiguous number is hashing. Hash algorithms come in all shapes and sizes depending upon their application needs. One nice hash is the Pearson hash which can make an 8-bit number of a string. For a reasonably comprehensive list of hash algorithms check out this List of hash functions. Generally hash functions are intended to convert some string into a unique number that is very unlikely to represent any other string. How unlikely depends upon the algorithm and the size of the number. For example, the Pearson hashes are quick and easy. They produce an 8-bit value using an XOR table. However, there are more than 256 words in the English language, much less the rest of the worlds languages, so the odds of a hash collision are quite high with a large set of words. However, it is relatively easy to manipulate the XOR tables so that there are no collisions for a small word set. Assuming we can apply some hash algorithm that will uniquely identify our words, it should be pretty easy to apply this technique to find our tokens. For example, in the first example we had the following table of keywords: const char *wordList[] = {"GPGGA","GNGSA","GPGSV","GPBOD","GPDBT","GPDCN"}; enum wordTokens {NO_WORD = -1,GPGGA,GNGSA,GPGSV,GPBOD,GPDBT,GPDCN}; What if, that changed to this: const int hashList[] = {<hash_of_GPGGA>,<hash_of_GNGSA>,<hash_of_GPGSV>,<hash_of_GPBOD>,<hash_of_GPDBT>,<hash_of_GPDCN>}; enum wordTokens {NO_WORD = -1,GPGGA,GNGSA,GPGSV,GPBOD,GPDBT,GPDCN}; It is not hard to imagine hashing the incoming word into an integer and then scanning the hashList looking for a match. This would be 2.5x smaller in memory if we did not need to store the master wordList and the comparison would be a 2 byte compare (or a 1 byte compare if we used a smaller hash). It would only require 2N comparisons where N is the number of words to check for. Of course hashing the incoming word creates an up-front cost but that cost could be buried inside the character receive function. The hash methods are not perfect. With any one-way algorithm on unknown input, there is the possibility of a collision. That is where two words have the same computed hash value. This could mean that two of the keywords have the same value, or it could mean that a randomly chosen word (or random characters) matches a valid input. In a system where the keyword list is static and known at compile time, it is possible to develop a "perfect hash". That is a hash that guarantees all valid inputs are unique. If your system is concerned about random "noise" being treated as valid data, there are at least two ways to solve this. Keep a list of the original words and do a final byte-for-byte compare one time. Add a checksum to the input and make sure the checksum has to be valid in addition to the hash match. For NMEA strings, this is already available. Can we go faster still? The integer compare search method works very well, but there are a few ways to go even faster. Sort the hashes in the list and use a search algorithm like a binary search to find the match. This reduces the the time from O(n) to O(log(n)). Much faster. Use the hash as an index into an array of the tokens. This reduces the time from O(n) to O(1). Much Much faster but makes a potentially HUGE array (2^<hash bit length>) Use the hash%<word count> to create a minimally sized table. This works but requires a minimal perfect hash. That is, a hash with the property of producing an N record table for N words. These algorithms are hard to find. Use the hash as the token in the rest of the system. Why bother looking up a token if you already have a nice number. This is a good solution but assumes that you never need to use the tokens as indices of other arrays. The idea that you can use the hash as an index into an array of records is the bases of a data structure called a Hash Table. Accessing a hash table is typically O(1) until a collision is detected and then it goes to O(m) where m is the number of items in the collisions. Typically the system implements the hash table as a sparse array with additional arrays holding the matching hash items. That is a lot of words. I think it is time for a few examples. First let us implement a basic hash search using our short word list. That was pretty easy but it is easy to see how finding a perfect hash function can get more and more difficult as we add words. Fortunately for us, there is a tool that is part of the GCC compiler suite called Gperf. Gperf's job is to find a perfect hash algorithm for a list of words and produce the C code to process it. Sounds perfect, so here is an example of how that works. First we must prepare a word list. The word list below shows a structure that will be used to store the word list in the C program. This is followed by the list of words and indices that will be used to populate an array of the structure. struct keyword_s {const char *name; int index;}; %% GPGGA,0 GNGSA,1 GPGSV,2 GPBOD,3 GPDBT,4 GPDCN,5 GPRMC,6 GPBWC,7 The word list is converted into C code with the following command line: gperf -t -I --output-file=hashTable.c keywordlist.txt This command will create a file called hashTable.c. Inside this file is one public function called in_word_set. Below you can see where I modified the NMEA_findToken function to use the in_word_set function supplied by gperf. enum wordTokens {NO_WORD = -1,GPGGA,GNGSA,GPGSV,GPBOD,GPDBT,GPDCN, GPRMC, GPBWC}; struct keyword_s {const char *name; int index;}; extern struct keyword_s *in_word_set (register const char *str, register size_t len); enum wordTokens NMEA_findToken(char *word) { enum wordTokens returnValue = NO_WORD; struct keyword_s *kw; kw = in_word_set(word,5); if(kw) returnValue = kw->index; return returnValue; } Compile and Run and you get the following results. Note how the hash search spends a fixed amount of time computing the 8-bit Pearson hash of the keyword. Then it spends a small amount of time searching for the hash value in the list of hash keys. This search is a brute force linear search. A binary search would likely be faster with a large word set, but with only 8 words in the word set most o the time its spent computing the hash. The GPERF code is very interesting. Notice how the function is fixed time if the word is present and is much faster when the word is absent. There are a number of options to GPERF to allow it to produce code with different strategies. If you look at the code produced by GPERF you will notice that there is a final test using strcmp (or optionally strncmp). This will eliminate the possibility of a collision. If we don't care about collisions, look how much faster this gets. STRNCMP IF-ELSE RAGEL -G2 Hash Search (Hash/Search) Hash GPERF Hash GPERF no compare GNGSA 399 121 280 326 167/159 374 126 GPGSV 585 123 304 288 167/121 374 126 GLGSV 724 59 225 503 167/336 113 113 GPRMC 899 83 299 536 167/369 374 126 GPGGA 283 113 298 440 167/273 374 126 So far I would have to say that the GPEF solution is easily the best way to decipher the sentences from my GPS. I know the GPS will deliver good strings so I would feel pretty comfortable stripping off the final compare. However, even with the string compare the GPERF solution is pretty good. It is only consistently beat by the hand-crafted if-else which will be a challenge to maintain. Perhaps we should consider writing a code generator for that method. Hashing is a very interesting topic with a lot of ratholes behind it. Some of the fastest algorithms and search methods take advantage of hashes to some degree. Our passwords also use hashes so that passwords can be compared without knowing what the actual password is. I hope this has been as informative to you as it was to write. As usual, take a look at the attached MPLAB projects to try out the different ideas. Good Luck. example4-PearsonSearch.zip example4 gperf.zip example4 gperf no compare.zip
  18. N9WXU

    Melbourne Weather

    Wow that could be Phoenix! Lots of evaporative coolers in the older parts of town. Leaves a mess on the roof! I am seeing them in Tucson as well.
  19. “Code generation, like drinking alcohol, is good in moderation.” — Alex Lowe This episode we are going to try something different. The brute force approach had the advantage of being simple and easy to maintain. The hand-crafted decision tree had the advantage of being fast. This week we will look at an option that will hopefully combine the simplicity of the string list and the speed of the decision tree. This week we will use a code generator to automatically create the tokenizing state machine. I will leave it to you to decide if we use generation in moderation. Let me introduce RAGEL http://www.colm.net/open-source/ragel/. I discovered RAGEL a few years ago when I was looking for a quick and dirty way to build some string handling state machines. RAGEL will construct a complete state machine that will handle the parsing of any regular expression. It can do tokenizing and it can do parsing. Essentially, you define the rules for the tokens and the functions to call when each token is found. For instance, you can write a rule to handle any integer and when an integer is found it can call your doInteger() method. For our simple example of identifying 6 words, the RAGEL code will be a bit overkill but it will be MUCH faster than a brute force string search and in the same ball park as the hand crafted decision tree. Let us get started. First let us get the housekeeping out of the way. This part of the code you have seen before. It is identical to the first two examples I have already provided. There are two differences. First, this only LOOKS like C code. In fact, it is a RAGEL file (I saved it with a .rl extension) and you will see the differences in a moment. When I use a code synthesizer, I like to place the needed command line at the top of the file in comments. While comments are a smell, this sort of comment is pretty important. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 // compile into C with ragel // ragel -C -L -G2 example3.rl -o example3.c // #include <string.h> #include <stdio.h> #include "serial_port.h" char * NMEA_getWord(void) { static char buffer[7]; memset(buffer,0,sizeof(buffer)); do { serial_read(buffer,1); } while(buffer[0] != '$'); for(int x=0;x<sizeof(buffer)-1;x++) { serial_read(&buffer[x], 1); if(buffer[x]==',') { buffer[x] = 0; break; } } return buffer; } enum wordTokens {NO_WORD = -1,GPGGA,GNGSA,GPGSV,GPBOD,GPDBT,GPDCN, GPRMC, GPBWC}; RAGEL is pretty nice in that they choose some special symbols to identify the RAGEL bits so the generator simply passes all input straight to the output until it finds the RAGEL identifiers and then it gets to work. This architecture allows you to simply insert RAGEL code directly into your C (or other languages) and add the state machines in place. The first identifiers we find are the declaration of a state machine (foo seemed traditional). You can define more than one machine so it is important to provide a hint to the generator about which one you want to define. After the machine definition, I specified the location to place all the state machine data tables. There are multiple ways RAGEL can produce a state machine. If the machine requires data, it will go at the write data block. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 %% machine foo; %% write data; enum wordTokens NMEA_findToken(char *word) { const char *p = word; const char *pe = word + strlen(word); int cs; enum wordTokens returnValue = NO_WORD; %%{ action gpgga { returnValue = GPGGA; fbreak; } action gngsa { returnValue = GNGSA; fbreak; } action gpgsv { returnValue = GPGSV; fbreak; } action gpbod { returnValue = GPBOD; fbreak; } action gpdbt { returnValue = GPDBT; fbreak; } action gpdcn { returnValue = GPDCN; fbreak; } action gpbwc { returnValue = GPBWC; fbreak; } action gprmc { returnValue = GPRMC; fbreak; } gpgga = ('GPGGA') @gpgga; gngsa = ('GNGSA') @gngsa; gpgsv = ('GPGSV') @gpgsv; gpbod = ('GPBOD') @gpbod; gpdbt = ('GPDBT') @gpdbt; gpdcn = ('GPDCN') @gpdcn; gpbwc = ('GPBWC') @gpbwc; gprmc = ('GPRMC') @gprmc; main := ( gpgga | gngsa | gpgsv | gpbod | gpdbt | gpdcn | gpbwc | gprmc )*; write init; write exec noend; }%% return returnValue; } Next is the C function definition starting at line 4 above. I am keeping the original NMEA_findToken function as before. No sense in changing what is working. At the beginning of the function is some RAGEL housekeeping defining the range of text to process. In this case the variable p represents the beginning of the test while pe represents the end of the text. The variable cs is a housekeeping variable and the token is the return value so initialize it to NO_WORD. The next bit is some RAGEL code. The %%{ defines a block of ragel much like /* defines the start of a comment block. The first bit of ragel is defining all of the actions that will be triggered when the strings are identified. Honestly, these actions could be anything and I held back simply to keep the function identical to the original. It would be easy to fully define the NMEA data formats and fully decode each NMEA sentence. These simply identify the return token and break out of the function. If we had not already sliced up the tokens we would want to keep store our position in the input strings so we could return to the same spot. It is also possible to feed the state machine one character a time like in an interrupt service routine. After the actions, line 21 defines the search rules and the action to execute when a rule is matched. These rules are simply regular expressions (HA! REGEX and SIMPLE in the same sentence). For this example, the expressions are simply the strings. But if your regular expressions were more complex, you could go crazy. Finally, the machine is defined as matching any of the rules. The initialization and the actual execute code are placed and the RAGEL is complete. Whew! Let us look at what happened when we compile it. One of my favorite programming tools is graphviz. Specifically DOT. It turns out that RAGEL can produce a dot file documenting the produced state machine. Lets try it out. bash> ragel -C -L -V example3.rl -o example3.dot bash> dot example3.dot -T png -O It would be nicer if all the numbers on the arrows were the characters rather than the ASCII codes but I suppose I am nitpicking. Now you see why I named my actions after the sentences. The return arrow clearly shows which action is being executed when the words are found. It also shows that the action triggers when the last letter is found rather than a trailing character. I suppose if you had the word gpgga2, then you would need to add some additional REGEX magic. The dotted arrow IN leading to state 17 refers to any other transition not listed. That indicates that any out-of-place letter simply goes back to 17 without triggering an ACTION. It is possible to define a “SYNTAX ERROR” action to cover this case but I did not care. For my needs, failing quietly is a good choice. This all looks pretty good so far. What does the C look like? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 /* #line 1 "example3.rl" */ // compile into C with ragel // ragel -C -L -G2 example3.rl -o example3.c // #include < string.h > #include < stdio.h > #include "serial_port.h" char * NMEA_getWord(void) { static char buffer[7]; memset(buffer, 0, sizeof(buffer)); do { serial_read(buffer, 1); } while (buffer[0] != '$'); for (int x = 0; x < sizeof(buffer) - 1; x++) { serial_read( & buffer[x], 1); if (buffer[x] == ',') { buffer[x] = 0; break; } } return buffer; } enum wordTokens { NO_WORD = -1, GPGGA, GNGSA, GPGSV, GPBOD, GPDBT, GPDCN, GPRMC, GPBWC }; /* #line 34 "example3.rl" */ /* #line 39 "example3.c" */ static const int foo_start = 17; static const int foo_first_final = 17; static const int foo_error = 0; static const int foo_en_main = 17; /* #line 35 "example3.rl" */ enum wordTokens NMEA_findToken(char * word) { const char * p = word; const char * pe = word + strlen(word); int cs; enum wordTokens returnValue = NO_WORD; /* #line 57 "example3.c" */ { cs = foo_start; } /* #line 62 "example3.c" */ { switch (cs) { tr5: /* #line 45 "example3.rl" */ { returnValue = GNGSA; { p++; cs = 17; goto _out; } } goto st17; tr12: /* #line 47 "example3.rl" */ { returnValue = GPBOD; { p++; cs = 17; goto _out; } } goto st17; tr13: /* #line 50 "example3.rl" */ { returnValue = GPBWC; { p++; cs = 17; goto _out; } } goto st17; tr16: /* #line 48 "example3.rl" */ { returnValue = GPDBT; { p++; cs = 17; goto _out; } } goto st17; tr17: /* #line 49 "example3.rl" */ { returnValue = GPDCN; { p++; cs = 17; goto _out; } } goto st17; tr20: /* #line 44 "example3.rl" */ { returnValue = GPGGA; { p++; cs = 17; goto _out; } } goto st17; tr21: /* #line 46 "example3.rl" */ { returnValue = GPGSV; { p++; cs = 17; goto _out; } } goto st17; tr23: /* #line 51 "example3.rl" */ { returnValue = GPRMC; { p++; cs = 17; goto _out; } } goto st17; st17: p += 1; case 17: /* #line 101 "example3.c" */ if (( * p) == 71) goto st1; goto st0; st0: cs = 0; goto _out; st1: p += 1; case 1: switch (( * p)) { case 78: goto st2; case 80: goto st5; } goto st0; st2: p += 1; case 2: if (( * p) == 71) goto st3; goto st0; st3: p += 1; case 3: if (( * p) == 83) goto st4; goto st0; st4: p += 1; case 4: if (( * p) == 65) goto tr5; goto st0; st5: p += 1; case 5: switch (( * p)) { case 66: goto st6; case 68: goto st9; case 71: goto st12; case 82: goto st15; } goto st0; st6: p += 1; case 6: switch (( * p)) { case 79: goto st7; case 87: goto st8; } goto st0; st7: p += 1; case 7: if (( * p) == 68) goto tr12; goto st0; st8: p += 1; case 8: if (( * p) == 67) goto tr13; goto st0; st9: p += 1; case 9: switch (( * p)) { case 66: goto st10; case 67: goto st11; } goto st0; st10: p += 1; case 10: if (( * p) == 84) goto tr16; goto st0; st11: p += 1; case 11: if (( * p) == 78) goto tr17; goto st0; st12: p += 1; case 12: switch (( * p)) { case 71: goto st13; case 83: goto st14; } goto st0; st13: p += 1; case 13: if (( * p) == 65) goto tr20; goto st0; st14: p += 1; case 14: if (( * p) == 86) goto tr21; goto st0; st15: p += 1; case 15: if (( * p) == 77) goto st16; goto st0; st16: p += 1; case 16: if (( * p) == 67) goto tr23; goto st0; } _out: {} } /* #line 66 "example3.rl" */ return returnValue; } int main(int argc, char ** argv) { if (serial_open() > 0) { for (int x = 0; x < 24; x++) { char * w = NMEA_getWord(); enum wordTokens t = NMEA_findToken(w); printf("word %s,", w); if (t >= 0) printf("token %d\n", t); else printf("no match\n"); } } serial_close(); return 0; } And this is why we use a code generator. The code does not look too terrible. i.e., I could debug it if I thought there were some bugs and it does follow the state chart in a perfectly readable way. BUT, I hope you are not one of those programmers who finds GOTO against their religion. (Though Edsger Dijkstra did allow an exception for low level code when he wrote EWD215 https://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD215.html ) So how does this perform? STRNCMP IF-ELSE RAGEL -G2 GNGSA 399 121 280 GPGSV 585 123 304 GLGSV 724 59 225 GPRMC 899 83 299 GPGGA 283 113 298 And for the code size MPLAB XC8 in Free mode on the PIC16F1939 shows 2552 bytes of program and 1024 bytes of data. Don’t forget that printf is included. But this is comparable to the other examples because I am only changing the one function. So our fancy code generator is usually faster than the brute force approach, definitely slower than the hand-crafted approach and is fairly easy to modify. I think I would use the string compare until I got a few more strings and then make the leap to RAGEL. Once I was committed to RAGEL, I think I would see how much of the string processing I could do with RAGEL just to speed the development cycles and be prepared for that One Last Feature from Marketing. Next week we will look at another code generator and a completely different way to manage this task. Good Luck. example3.X.zip
  20. The PICmcu is not known for being fast or supporting large memories but it does have one feature that can significantly simplify developing your applications. That feature is the lack of a hardware call stack. Sacrilege you say! But wait... The lack of this important feature has caused the compiler team to develop an incredibly useful alternative that I would argue is better in nearly every way than an actual stack. For those of you who are now wondering what I am talking about, let's take a quick diversion into stacks. A stack is simply a data structure that arranges a number of data elements so that the last thing you inserted is the first thing you get back. Think of a stack of plates, you add plates to the top of the stack and remove them in reverse order from the top of the stack. This is important for a few reasons. First, imagine your code was interrupt by a hardware interrupt. The current address of your code is pushed onto the stack, the interrupt runs and your address is popped from the stack so the interrupt can return where it interrupt you. This is a handy feature and for "free" you can handle any number of interruptions. In fact, a function can call itself and so long as there is sufficient room on the stack, everything will be sorted out on the return. Now, the PICmcu's have hardware stacks for the the function calls and returns. They simply don't have any hardware support for anything else. If the hardware stack is so useful for keeping track of return addresses, it would also be useful for all the parameters your function will need and the values your functions will return. This parameter stack is an important feature of most languages and most especially the C language. The AVR, ARM, 68000, IA86, Z80, VAX11, all have instruction level support for implementing a parameter stack for each function. I have written millions of lines of C code for the PIC16 so how does it do its job without this important part of the language and why do I think this missing features is such a strong strength of the CPU. The secret to the ability of XC8 to produce reasonably efficient C code for the PIC16 and PIC18 without a stack lies in the "compiled stack" feature. This feature analyses the call tree of your program and determines what the stack would look like at any point in the program. Functions that could be in scope at the same time (consider a multiply function in "main" and the interrupt) are duplicated so there are no parameters that need to be in two places at the same time. Any recursive functions are detected and the user alerted. Finally, the complete stack is converted to absolute addresses and mapped into the physical memory of the CPU. Then all the instructions are fixed up with those absolute addresses. This big-picture view of the program also allows the compiler to move parameters around to minimize banking (banking is extra instructions required to reach addresses further than 128 bytes away) and finally, the finished program is ready to run in your application. The amazing thing is the final memory report is the complete memory requirements of the program INCLUDING THE LOCAL VARIABLES. This is a shocker. In fact, when I was looking at the Arduino forums,. I would frequently encounter users who added one more line of code and suddenly their application stopped working. They were told to go buy the bigger CPU. Imagine if your compiler could tell you if the program would fit and that would include all the stack operations. This is a game changer and I would love to see the industry apply this technology across all CPU's. There is no reason why any CPU would not be able to operate with a compiled stack. In fact, most CPU's are capable of operating with both kinds of stacks at the same time. The biggest reason against this sort of operation is really in large project management. Consider, you develop a library for some special feature, perhaps GPS token parsing, Now you want to include this library in all of your applications. You MUST NOT recompile this code because it has passed all of your certification testing and is known good "validated" code. (remember, the compiler is permitted to produce a different binary on each run). If you cannot recompile the code, on some architectures you cannot change the addresses as there could be side effects (banking on a PIC16). If your code only relies upon a stack, then there is never any recompiling required and the linker task is dramatically simplified. Anyway, I must go back into the FreeRTOS world and continue my quest to find the thread with the overflowing stack. Life would be simpler with static analysis tools for the stack. Until next time.,
  21. While we are on the topic of the wisdom of Dijkstra let us not forget what he said about computer architecture. I refer you to EWD 32, Paragraph 5. http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD32.html The first time I read that I almost fell on the floor. It is so true. Most of the time we are awed every time the CPU architects have clearly anticipated our needs and built the correct facilities into the MCU's. But occasionally, you get a strange oversight like the TRMT bit without an interrupt in the EUART on PICmcu's. Or the advanced math options on the ADC with Computation but they work on every conversion and don't respect the channel. i.e. you are limited to operating on a single ADC channel if you use the advanced features. We all need a good laugh, so post your favorites "features" below.
  22. When we left off we had just built a test framework that allowed us to quickly and easily try out different ways to identify NMEA keywords. The first method shown was a brute force string compare search. For this week, I promised to write about an if-else decoder. The brute force search was all about applying computing resources to solve the problem. This approach is all about applying human resources to make life easy on the computer. So this solution will suck. Let us press on. The big problem with the string compare method is each time we discard a word, we start from scratch on the second word. Consider that most NMEA strings from a GPS start with the letters GP. It would be nice to discard every word that does not begin with a G and only look at each letter once. Consider this state machine: I did simplify the drawing… every invalid letter will transfer back to state 1 but that would clutter the picture. This would require the smallest number of searches to find the words. So one way to build this is to write a big IF-ELSE construct that covers all the choices. This will step through the letters and end up with a decision on what keyword was found. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 enum wordTokens NMEA_findToken(char *word) { enum wordTokens returnValue = NO_WORD; char c = *word++; if(c == 'G') { c = *word++; if(c == 'P') { c = *word++; if(c == 'G') // gpGga or gpGsv { c = *word++; if(c == 'G') // gpgGa { c = *word++; if(c == 'A') { if(*word == 0) // found GPGGA { returnValue = GPGGA; } } } else if(c == 'S') // gpgSv { c = *word++; if(c == 'V') { if(*word == 0) // found GPGSV { returnValue = GPGSV; } } } } else if(c == 'B') // gpBod { c = *word++; if(c == 'O') { c = *word++; if(c == 'D') { if(*word == 0) { returnValue = GPBOD; } } } } else if(c == 'D') // gpDcn or gpDbt { c = *word++; if(c == 'C') { c = *word++; if(c == 'N') { if(*word == 0) { returnValue = GPDCN; } } } else if(c == 'B') { c = *word++; if(c == 'T') { if(*word == 0) { returnValue = GPDBT; } } } } } else if(c == 'N') // gNgsa { c = *word++; if(c == 'G') { c = *word++; if(c == 'S') { c = *word++; if(c == 'A') { if(*word == 0) { returnValue = GNGSA; } } } } } } return returnValue; } And it is just that easy. This is fast, small and has only one serious issue in my opinion. I hope you are very happy with the words chosen, because making changes is expensive in programmer time. This example only has 6 6-letter words and is 100 lines of code. They are easy lines, but almost all of them will require rewriting if you change even one word. Here are the stats so you can compare with last weeks string compare. STRNCMP IF-ELSE GNGSA 399 121 GPGSV 585 123 GLGSV 724 59 GPRMC 899 83 GPGGA 283 113 These are the CPU cycles required on a PIC16F1939. You can verify in the simulator. That is all for now. Stay tuned, next time we will show a nice way to manage this maintenance problem. Good Luck example2.c example2.X.zip
  23. My Favorite is "the real world" == Violent anti-intellectualism
  24. Ok. That looks more like what I suspected. Thanks for checking the math. That 1/2% error budget in x4 mode will be challenging for most systems. You will need short cables and/or low baud rates.
  25. Those are great questions. So here is the answer with the same procedure. 10 bit-times * 16 provided 160 total sample times in a byte. The error threshold occurs 1/2 a bit time early so you subtract 8 sample for 152 total sample times as the baseline. Then the article assumed additional errors of ±25% and ±37.5 for the two test cases. .25 * 16 == 4 and .375 * 16 == 6 less 1 bit for sampling uncertainty and you get ±3 and ±5 sample times of allowable mismatch out of 152 sample times. If we rework the numbers for x4 sampling and x8 sampling we get the following: x4 Sampling (PIC BRGH = 1) 10 * 4 == 40 - 2 == 38 total sample times. .25 * 4 == 1 and .375 == 1.5. less 1 for sampling uncertainty and you get ±0 and ±1 (rounded .5 up to 1 for a 'good" link) So you just can't receive a bad link (50% chance of catching the last bit) and on a reasonable link (75% chance of catching the last bit) you have a 1/38 == ±1.3% link budget. If BRGH is set, you need a fantastic signal and you get a ±2% link budget. x8 Sampling (AVR U2Xn bit set) 10 * 8 == 80 - 4 == 72 total sample times to the edge of acceptability. .25 * 8 == 2 and .375 * 8 == 3 less 1 for sampling uncertainty and you get ±1 and ±2. Total Link Baudrate Error is 2/72 == ±2.7% and 3/72 == ±4.2%. Essentially, the lower oversampling means the middle is sampled more broadly which increases area where the edges can be caught.
×
×
  • Create New...