Introduction The TDS7104 Common Failures Make an Image of the Hard Drive CR2032 Backup Battery Replacement and Display Brightness Do NOT Remove the Front Panel Scope Disassembly A Failed Attempt at Switching over to an SSD Reinstalling from Scratch: Windows 2000 Pro or Windows XP? Not All TEAC CD-224E Drives are the Same Installing Windows 2000 Pro on an Old Machine through a Virtual Machine Burning the Windows 2000 Pro Installation Disk onto a USB Stick Booting from USB Stick with a Plop Boot Manager Installing Windows 2000 Pro Installing Special TDS7104 Drivers Installing Tektronix Firmware The Scope is Working! Re-enabling the Existing License Cleaning Up The End References Footnotes Introduction A little over a month ago, I ran into a Tektronix TDS7104 at the Silicon Valley Flea Market, where else? Other than some dirty buttons, a few smudges here and there, and the usual assortment of calibration and asset tracking tags, the unit was in excellent cosmetic shape, but the price tag of $700 was way out of line: as I write this a try-before-you-buy TDS7104 can be had on Craigslist for the same price. But Paul, the seller/liquidator, has a habit of saying “I’ll make you a deal” and he did before I even asked: $300. That’s still a lot by flea market standards, but a pretty good price for a TDS7104… if you can get it to work. At home, the scope powered up right away and it booted straight into the main scope application. Other than a screen that was way too dim, everything seemed fine. But when I tried it again a few hours later, it got stuck at the BIOS screen with a CMOS battery error. In this blog post, I go over the steps I took to get the scope back in top shape. The TDS7104 The TDS7104 is a 4-channel oscilloscope with 1 GHz bandwidth and a maximum sample rate of 10Gs/s, though that’s only possible when using 1 channel. The sample rates drop to 5 Gs/s for 2 channels and 2.5 Gs/s for 3 or 4. Even by today’s standards, the specs exceed those of hobbyist class oscilloscopes, think Rigol and Siglent, though there’s a price to pay in terms of weight, 39 pounds, and volume: they’re as wide and deep as the earlier TDS700 series, for example, and much taller. The TDS7054 is its little brother, figuratively speaking only. In the same chassis, it has a 500 MHz bandwidth and 5 Gs/s. Unlike more advanced TDS7xxx models, the 7104 and 7054 have BNC connectors instead of custom Tektronix ones that require probes or adapters with prices that exceed today’s price of the scope itself. Introduced mid 2000, these scopes initially ran Windows 98 but they must have upgraded soon after to Windows 2000 Pro Embedded, because that’s what mine has and it has components with a late 2000 timestamp. The PC motherboard has the little-used NLX form factor. Mine was a RadiSys SF810 with a Socket 370 and a 100 MHz front-side bus. Originally, these scopes shipped with a dog slow 550 MHz Celeron, I got lucky with a 850 MHz Celeron. The fastest compatible Celerons with 100 MHz FSB go up to 1.4 GHz, but they’re pricy. You should be able to find 1.1 GHz versions for around $20 on eBay. Unlike my Agilent 54831, the 640x480 LCD screen has resistive touch control which makes it possible to use the advanced scope features without the need to connect a mouse. In addition to the PC motherboard, there is a PowerPC-based controller board that runs VxWorks like many other Tektronix products of that time, and a large acquisition board. In addition to a few hardware options such as a 4M/channel sample memory, up from a 500k default, there are plenty of software options for advanced measurements: jitter testing, USB certification testing, etc. Both the software and hardware options can be enabled with a license key. To the suprise of no one, that protection scheme was hacked long time ago… According to the labels on the chassis, my scope came from the PSD lab at Cypress Semiconductor, where it was used for things like measuring high-bandwidth signals such as the battery current on the Apple TV Remote. :o) Common Failures As always, you’ll find a bunch of hobbyists trying to revive this kind of scope on the EEVblog forum, Youtube and some blogs. Here are the most common failures: PC motherboard CMOS backup battery dead PowerPC backup battery dead Hard drive dead Power supply capacitors leaking I was lucky and only had to deal with issues 1 and 3, sort of. Make an Image of the Hard Drive Whether the machine boots or not, your first step should always be to make an image of the hard drive, a 6 GB IBM Travelstar in my case. Like my Agilent 54831, I thought that I’d have to open the case to access the drive, but you can just push on the spring-loaded black cover in the back and pull the drive sled out1. Nice! Remove the drive from the sled, plug it into a USB-to-IDE adapter, and extract the data. On Windows, I use HDD Raw Copy Tool. I often use Linux for this kind of maintenance, but since this scope is a Windows 2000 machine, I ended up needing a bunch of Windows-only tools. The Travelstar HD was running on fumes, because HDD Raw Copy Tool ran into a number of corrupt sectors during the copying operation. I was lucky, the impacted files were related to the French Windows 2000 manual, but it shows the importance of making an image of the drive ASAP. CR2032 Backup Battery Replacement and Display Brightness You’ll need to open up the case to get to the PC motherboard CR2032 backup battery. See the next 2 sections for that. After installing the new CR2032, the scope booted back up again, but the TekScope window had some weird corruption and waveforms didn’t render right. This was because the Chips & Technologies 69000 graphics card settings had been changed to a 256 color palette mode. It needs to be set to True Color 24-bit mode.2 Notice the presence of 2 video cards: an Intel 810 integrated graphics card and the Chips & Technologies 69000. The latter is responsible for driving the LCD screen. It has special hardware to render oscilloscope waveforms in overlay mode: they are sent by the acquisition board to the video memory through DMA3 without CPU intervention. While we’re on the topic of the display: after installing the CR2032, the LCD display was still very dim, to the point that I was researching replacement CCFL backlight tubes. That turned out to be entirely unnecessary: the TDS7104 doesn’t have a way to control the intensity of the LCD backlight. The previous users must have used it in a dark lab and dialed down the brightness by adjusting the gamma settings in Windows: Do NOT Remove the Front Panel I’m putting this section before the Disassembly one to make sure those with a low attention span get the message: chances are high that you don’t need to remove the front panel. And that’s good because, unlike the TDSnnn series scopes, the front panel has some plastic tabs that are very easy to break. That said, even if you do break them (I did!), the result is not catastrophic and you should be able to put the panel back firmly where it belongs with no one noticing a thing. (Click to Enlarge) The TDS7000 Series Service Manual makes it sound easy enough: To remove the trim ring, slide the flat end of a soldering aid into the side slot on the trim ring. Press in, then lift up to hook it underneath, then pry up. And from the pictures, it’s as if you can remove the front panel without removing anything else. That just didn’t work… The front panel consists of multiple click tabs: 1 on the left side, 1 on the right and then a bunch at the top and the bottom. So far so good. However, the left and right side also have 2 slide tabs that go into the metal rails. If you lift the left and right tabs too much, these plastic slide tabs break off. So you need to be very careful to make sure that you don’t lift the plastic trim too much, and that you slide the panel out while it stays parallel with the display. Or… you don’t touch it: you can do all PC maintenance, including replacing the floppy drive, without removing the front panel. Scope Disassembly I will continue my tradition of documenting the disassembly of test equipment in too much detail because nobody else does it. Even though the service manual technically describes how to do it, a few pictures go a long way to make it easier. To access the inside of the scope, you need to remove more than 30 screws. On the plus side, they’re all Torx-15 screws and they’re all the same length, so you don’t need to worry about keeping track of which screw goes where. Still, it takes a while and it validated my recent purchase of this cordless screwdriver, recommended by Shrirar over at The SignalPath. Unbutton the accessory bag This took me longer to figure out than I want to admit: you can just unclick the bag from the chassis, but the buttons can be very tight and if you’re not careful the fabric can tear. Use a flat-head screwdriver right next to each button to lever it off. Put the scope upright on its back feet It’s an unusual arrangement, but the easiest way to dismantle the scope is by putting it on its back feet: you don’t need to remove any screw from the back! Let me once again sing the praises of a sturdy equipment cart: it’s so much easier to walk around the cart than to muscle around bulky, heavy test equipment on a table. Remove the top panel 4 screws through the accessory bag buttons (“snap studs”) fix the top panel to the chassis. After removing this panel, you could remove the side panels already, but I found it much easier to remove the bottom panel next. Remove the bottom panel and loosen the black front connector trim Next, remove the 5 screws of the bottom panel as well as 3 screws that keep the black trim of the front BNC connectors in place. The black trim doesn’t need to be completely removed, only loosened because otherwise it will soon be in the way of some other screws. The bottom panel shall now be removed though. Just slide it down a bit and take it off. In the picture above, you can see 2 screws that aren’t marked in red. That’s because they don’t keep the bottom panel in place. But if you feel like it, you might as well remove them now too. Remove the handle and side panels With the bottom panel gone, the side panels are a breeze to remove after unscrewing the handle. I lied: these 2 screws are different than the others. But they’re a different color and impossible to get wrong. Remove the 2 sheet metal parts With the outer covers removed, you’re now staring at the sheet metal RF protection enclosure. It consists of 2 parts, each part covers 2 sides. Remove all the screws, take off the bottom part and then the top. Note how some of the bottom screws are hidden underneath the BNC connector cover. That’s why you had to remove its 3 screws of the black trim. Congratulations! For those who didn’t keep track: you’ve removed 32 screws! After removing the panels, you now have access to the acquisition board at the bottom and the PC motherboard at the top: One side has nothing but cooling fans, but from the other side you can see the power supply and an RS-232 port that you will need to connect if the backup battery of the PowerPC controller board expires. If you need access to those items, you’ve only done the easy disassembly part. On my unit, both the PSU and the controller backup battery were fine so I was done. Note on the picture above that the front panel has been removed. You do NOT have to do this for pretty much all restoration cases! And you really shouldn’t. Reinstall the bottom sheet metal cover All of my work on the scope was on the PC motherboard and I had to put the scope back in its horizontal position. To make sure that I didn’t accidentally damage the acquistion board, I put the bottom sheet metal cover back in its place. A Failed Attempt at Switching over to an SSD I’ve been using CompactFlash cards in the past to replace ailing hard drives. They work, but unless you buy a more expensive “industrial” card, they don’t have built-in wear leveling support. That is not a problem on a Rohde AMIQ that runs DOS, but on an OS like Windows with swap space, it could be4. So this time, I chose a 64 GB mSATA SSD ($35) and an mSATA SSD to IDE 44 Pin 2.5” adapter ($15)5. The standard way to move away from a failing hard drive to an SSD is to once again use HDD Raw Copy Tool to write the image to the SSD and that is that. I tried that with the 64 GB SSD, and while the scope got past the first-stage boot process, it errored out during the second stage when it tries to bring up the Windows GUI with a STOP: c0000218 {Registry File Failure} error. Older systems often had issues with partitions larger than 32 GB, so I bought a 32 GB mSATA SSD instead, $3 cheaper for half the capacity, but I got the same error. Just copying the drive image to an SSD worked fine for others, but for me it was a dead-end that I spent many hours trying to get around. I eventually decided to reinstall all the software from scratch, which was a whole other adventure. Reinstalling from Scratch: Windows 2000 Pro or Windows XP? I had wanted to avoid reinstalling the OS from scratch because I expected to run into a bunch of driver issues, but in the end I had no choice. While a number of people have reported that Windows XP can work on some of the TDS7104 motherboards, I decided to stick with Windows 2000 Pro because I know that works and I didn’t have a pressing need for more functionality, whatever that might be. The scope has Windows 2000 Pro Embedded, but I wasn’t able to find an installation disk for that and the regular version works fine too. The ISO file can be downloaded from the Internet Archive. The license key that’s printed on the back to the scope does not work with the regular Windows 2000 Pro. The Internet Archive one has a key that works, and other valid keys are just a Google away, but I didn’t even need one: I was never asked for a license key during the Win2k installation on the scope. The standard way to install Win2k Pro is with a CDROM drive. Unfortunately, the drive didn’t work which meant I had to open the whole machine again to install a replacement drive. Not All TEAC CD-224E Drives are the Same The TEAC CD-224E laptop drive in my TDS7104 got detected just fine by the BIOS and in Windows, but when you inserted a disc in the drive, neither the BIOS nor Windows could read from it. Since the RadiSys motherboard doesn’t support booting from USB stick, I decided to replace the TEAC CD-224E laptop drive with a ‘new’ one that I got from eBay for $20. Unlike the hard drive, the CDROM drive can’t be removed without opening up the TDS7104, but once the case is open, the effort is minimal. I first removed the floppy drive to have a bit more maneuvering freedom with the cables, but it’s not really necessary. Unplug the CDROM IDE cable Remove 2 screws The CDROM drive sits in a metal enclosure with a small adapter PCB that converts the CD-224E 50-pin slimline IDE connector to a standard PATA/IDE connector. I tested the broken drive with the adapter PCB and my USB-to-IDE dongle on my laptop to make sure the issue was with the drive and not the CDROM disc, and that didn’t work, as expected. With the new CD-224E/dongle combo, my laptop could read the installation CD just fine, but when I installed the new drive in the TDS7104, the BIOS couldn’t even detect the drive! I tried every BIOS setting under the sun, but no luck. There are many versions of the CD-224E, all with the same dimensions and slimline IDE interface, but clearly they don’t all behave the same. The version of the broken one is version A93 (2000), the new one is CD0 (2005). You can find A93 drives on eBay, but $69 is way too high for something that I’d be using exactly once. Installing Windows 2000 Pro on an Old Machine through a Virtual Machine (Another dead-end) It is allegedly possible to install Windows 2000 Pro on an old machine without CDROM and USB port by using a virtual machine. The process is convoluted: mount the installation CDROM ISO and the SSD onto the virtual machine. go through the first phase of the installation process until asked to reboot. now move the SSD to the old the machine (the scope) and proceed with the installation there. I once again spent a few hours getting this to work, but the scope never managed to make it to the Windows installation GUI. Burning the Windows 2000 Pro Installation Disk onto a USB Stick Alright, so I’m running out of options and USB is about the only storage interface left. The scope can’t boot from a USB stick directly but there is a way around that. Let’s first create a bootable USB stick with the Win2k installation ISO on it. Most of the time, you can use a utility like Balena Etcher to burn a CDROM ISO onto a USB stick, but of course that doesn’t work for the Windows 2000 Pro installation CDROM. Instead, you need to use WinSetupFromUSB to prepare the USB stick: Download, install, launch Select the USB stick as target Select Auto format with FBinst and use the FAT32 file system Add to USB disk: Windows 2000/XP/2003 Setup Select the mounted Win2K Pro ISO drive as source Press “GO” to copy Win2K Pro onto the USB stick Booting from USB Stick with a Plop Boot Manager Plop Boot Manager makes it possible to boot from a USB stick on machines that don’t support it. It goes like this: copy the plpbt.img image from the plpbt-5.0.15.zip archive to a floppy disk with a tool like WinImage, Rawrite32, or RawWrite for Windows.6 boot the Plop Boot Manager from floppy disk. the boot manager has a USB mass storage device driver select USB as boot device I tried hard to avoid the floppy disk route because my experience with floppy drives on old test equipment has been abysmal: none of them worked. Having no choice, I tried to copy the boot manager image with my USB floppy drive and… that didn’t work either. All these years the USB floppy drive, freshly bought from Amazon, was the culprit! Since the scope still worked fine with the IBM HD, I used its own floppy drive to put the image onto the floppy disc and that worked. After setting the BIOS to allow booting from floppy, the scope booted into the Plop Boot Manager just fine and it was able to boot the USB stick with the Windows 2000 Installation ISO. Plop doesn’t support USB hubs. The RadiSys motherboard has only 1 USB port which will be occupied by the USB stick, so you’ll at least need a PS/2 keyboard to do anything. Installing Windows 2000 Pro With the empty 32GB SSD plugged into the scope, the installation of Windows 2000 Pro was uneventful. There are 2 phases: the first one uses text mode and primarily copies all the necessary drivers onto the SSD. The machine then reboots and continues the installation in Windows GUI mode from the SSD, though the USB stick is still needed in a later stage. The TDS7104 has a bunch of specialty hardware that needs dedicated drivers, but those are not needed to get the OS up and running. At long last, I was able to see this image: Installing Special TDS7104 Drivers There is a great GitHub repo with a bunch of TDS7000-series software, including this Drivers directory. The README.md says that the driver should work for Windows 98 and XP, but the Chips and Technologies video driver definitely did not work for Win2k!7 I used Driver Collector to extract drivers from the original hard drive and that worked fine. You can find these drivers here. The 4 specialty drivers are for these components: Front panel This is the USB Device that’s listed under “Other Devices” Texas Instruments PCI-1225 CardBus Controller You need to install this driver twice, once for each port. Windows installed a default PCI-1225 driver for this, but that one doesn’t work, hence the exclamation mark next to it. The name of the driver .inf file is unsup.inf, for unsupported? Confusing, but that’s the one to use. PCI2PCI bridge That’s the Other PCI Bridge Device. Chips and Technologies 69000 video driver The default Windows driver for the C&T 69000 is what makes the screen work when running Windows, but it’s not sufficient to render measured signals in the TekScope application. For that, you need to update to the Chips and Technologies (Asiliant) 69000 driver. Installing Tektronix Firmware The TDS7104 and TDS7054 firmware v2.5.5 can be freely downloaded from the Tektronix website. The installation was painless, just launch the executable. The TDS7104 has a convoluted architecture where the PowerPC on the controller board can access files on the hard drive of the regular PC that are located in the c:\vxboot directory. Since the controller backup battery on my scope was still in good condition, I didn’t have to do anything special: the vxboot directory was created automatically during the firmware installation. One thing that was missing, though, was the advanced jitter license option. The Scope is Working! And with that, I finally had a working TDS7104 with SSD! The time from pressing the power button to having a waveform on the screen was much lower too: from 2min50s down to 1min35s. Re-enabling the Existing License The same GitHub repo that I mentioned earlier also has an unlock options directory with scripts to enable and validate license key features. On the Eevblog forum, plenty of people have been able to use it, but it’s not as user-friendly as other license key schemes. Most of the time, license keys are additive, with one license key per feature that must be enabled. On the TDS7104, there is 1 license key that enables all features at once. The validate script shows how that works with the license key and serial number of my scope: ./validate.py BREHZ9885D3MNKXHHYQCQRGQRW7C E1 91 73 BF F7 7B E4 C5 52 3D C7 3A E1 9E 71 8F 76 01 44 2F 54 00 00 C0 1B 79 48 00 00 00 00 00 00 00 00 A8 16 30 00 10 00 00 00 00 00 This key is for UID 1BC00000542F (S/N 21551, model TDS/DSA/DPO7104): CRC: 4879 Key is valid, active options: 00 00 00 00 00 00 00 00 08 00 00 00 00 00 00 00 00 00 We can see how that long string of gibberish contains: the serial number 21551 the model number TDS/DSA/DPO7104 a UID that is really just a combination of the serial number and the model a CRC an 18-byte or 144-bit bitmask I can recreate the license key by feeding these parameters back in the generation tool: ./gen.py tds7104 B021551 000000000000000008000000000000000000 XBGDV-K8GDM-KH7X3-979Y9-ZZ593-9ZRZZ-4837X-9VV5Z-T9HB I had to join the 18 bytes into one 72-digit hex number. The license key that comes out doesn’t match the original one, but after entering it into my scope, it worked just the same: The scope is very forgiving about the license keys: upper case, lower case, dash or no dash, it all seems to work. You can even reduce the number of hex digits in the license enable mask to a certain extent, and the license key will still work: ./gen.py tds7104 B021551 000000000000000008000000000000 7GWUZ-RRRMK-59LYT-978Y8-GZD93-8ZQGZ-C836X-8CVD What remains is the question which bit maps to which feature? This post in the eevblog forum has you partially covered here: ######################################################################## 4 # options masks/names/descriptions, conversion functions 5 6 # 01 - 1M 7 # 02 - 2M 8 # 04 - 3M 9 # 06 - 2M 2A 10 # 08 - 4M 11 # 00 00 00 00 00 00 04 - USB 12 # 00 00 00 00 00 00 20 - JT3 13 # 00 00 00 00 00 00 00 80 - ET3 14 # 00 00 00 00 00 00 00 00 08 - JA3 15 16 # 00 00 05 00 00 00 00 00 00 10 - ASM DDRA DJA 17 # 00 44 00 00 00 00 02 08 - SM ST J1 J3E 18 # 04 40 00 00 00 00 06 C0 10 - 3M JT2 USB2 ST 19 # 04 44 FF 03 00 00 8D A3 EF FF 17 - 10XL, MTH, PTH1, ASM, LT, DDRA, SLE, EQ, TDSDDM2, TDSUSB2, YDSCPM2, RTE, IBA, PCI, TDSDVI, TDSET3, SAS, TDSHT3, TBD, JA3, TDSPTD, TDSVNM, DPOPWR, TDSHT3v1.3, 73, 74, DJE, DJA, 77, 78, 79, SVE, SVP, SVM, SLA Note how JA3, advanced jitter analysis, indeed has bit 14 set to 1. Some people just use a mask of FFFFFFF....FFFF. Some of these analysis tools can once again be found in the same GitHub repo, or on the Tektronix website. This is all theoretical, of course. I don’t think I’ll ever have a hobbyist need for any of this… Cleaning Up The final act is cleaning. This scope was in exceptional condition, except for the knobs on the control panel. The knobs have a thin anti-slip layer on them that is a finger grease magnet. Removing that layer with isopropyl alcohol makes the knobs look like new without a noticeable difference in control. Just be careful about using 99% isopropyl, I think it attacks the plastic. 90% was fine. If some knobs are missing or cracked, the ones of a TDS220 are identical. You can buy knobs new or on eBay, but they’re expensive. If you really need a few, you might be better off buying a donor TDS220 instead. The End And with that, the scope is ready to be deployed to a shelf in my garage. One day I’ll need something with this kind of firepower but for everything else, a small scope with lower specs is way more practical. I like the scope better than the Agilent 54831 so that will probably hit Craigslist at some point. All words in this blog posts were written by a human. References TDS7000 Series User Manual TDS7000 Series Service Manual Eevblog forum - Tek CSA7404/TDS7000 repair project This is the place to go. Chances are that all your questions will be answered here as long as you have the patience to read through 41+ pages of discussion. TDS7054 repair Github Repo with a lot of resources Footnotes I obviously only figured this out after removing the enclosure… ↩ I didn’t try the 16-bit not-so-true color mode. ↩ The Agilent 54831 uses a similar overlaying method. ↩ In reality, I will never use this scope enough to ever run into an issue like this. ↩ You can still find native 2.5” IDE 44 laptop SSDs, like this one, but you pay $30 more for the same capacity. ↩ RawWrite for Windows is the one to use on a 32-bit Windows system, like the Win2k OS on the IBM Travelstar of the scope. ↩ If you install the incorrect driver, the scope will still boot with a working LCD screen, but once the Windows GUI starts, it will move its business to the Intel integrated GPU. You need a VGA monitor to follow what’s happening. Even if you later select the right driver, Windows somehow thinks that the old driver is good enough and just doesn’t do it, without any feedback. I had to manually delete the bad driver files from the SSD to finally make it work. ↩

Introduction A Galois Field Introduction by Example Base Galois Fields A Real World Example of a Base Galois Field GF(2) Extended Galois Fields Extended Galois Field Addition Extended Galois Field Multiplication A Field Defining Irreducible Polynomial A Primitive Polynomial From Abstract Alpha to a Real Value Selecting Primitive Polynomials The Benefit of Primitive Polynomials Linear Feedback Shift Register Multiplication through Addition of Exponents References Footnotes Introduction In my blog post about Reed-Solomon coding, I used regular integers for all calculations. These are impractical for a real-world implementation, but since everybody knows integer math since first grade, it made things easier to learn things one step at a time. Instead of working with pure integers, actual Reed-Solomon implementations use elements from a Galois or finite field as symbols. I’ve been sitting on implementing and writing about a Reed-Solomon decoder for almost 4 years now1, and I’m still not quite there, but a first step is to have enough Galois field understanding so that the lack of it isn’t an obstacle. That’s what this blog is about. Don’t expect a solid theoretical treatise, you can find many of those as part of university courses, but something that is sufficient to refer back to in the future when I’ve forgotten some of the details. If you want to get a deeper understanding, check out the references at the bottom. A Galois Field Introduction by Example In mathematics, a field is a set of elements for which addition, subtraction, multiplication and division operations have been defined, with properties that we take for granted when dealing with rational or real numbers, such as the associative and distributive properties2, the rules for adding and multiplying with 0, and so forth. For rational or real numbers, the number of elements in the field is infinite. A Galois field only has a limited number of elements, yet still has these kind of operations and properties. A good example of a Galois field is \(\text{GF}(5)\) which has integer numbers 0 to 4 as elements. Addition, subtraction, and multiplication work the same as for regular integers but each such operation is followed by a modulo 5 operation. Here are a few example operations in \(\text{GF}(5)\): Division is a bit less intuitive. It is defined as the multiplication by the inverse of the divisor: One way of finding the multiplicative inverse of the divisor is by multiplying it with all possible elements and checking if the result is 1. Let’s say we want to do \(2/3\) in \(\text{GF}(5)\). We need to find \(3^{-1}\) so that \(3 \cdot 3^{-1} = 1\). There are 5 different options \(0,1,2,3,4\): We can see that \((3 \cdot 2)\bmod 5 = 1\), so \(3^{-1}=2\). And thus: There are other ways to calculate the multiplicative inverse. For simple cases, you can use Fermat’s Little Theorem, which says: or, after dividing both sides by \(a\): In our example \(a=3\) and \(p=5\), so: A more general algorithm is the Extended Euclidean Algorithm. Base Galois Fields The example above is one of a base Galois field \(p\) is the base number of a one-dimensional mathematical universe. In a base Galois field, \(p\) must always be a prime number, otherwise the division operation would be ill defined. For example, if we’d set \(p=6\) and tried to find the multiplicative inverse of 2, we’d get the following: There’s no solution with a result of 1. Since there’s at least one element for which a multiplicative inverse doesn’t exist, you can’t create a field for \(p=6\) and thus \(\text{GF}(6)\) can’t exist. Another issue for \(p=6\) is that you can get a result of 0 when multiplying 2 non-zero numbers: That’s behavior unbecoming of a proper field! A Real World Example of a Base Galois Field Since a base Galois field must have a prime number of elements, only \(\text{GF}(2)\) maps directly to the zeros and ones of digital logic; all other fields have an odd number of elements. Still, there are some real-world cases where these kind of Galois fields are used: the Wikipedia article on Reed-Solomon error correction has an example that uses \(\text{GF}(929)\), a field that is used for coding PDF417 bar codes. © Markus.Jungbauer - Wikipedia Modulo 929 calculations are fine for bar codes, you only need to process a few per second at most, but they’re not something you’d want to use for high speed communication protocols that run at rates of gigabits or bytes per second. GF(2) Before taking the next step, let’s first look at the only base field that maps neatly to ones and zeros: \(\text{GF}(2)\). The binary Galois field only has 2 symbols: 0 and 1. It has the following addition table: And this is the multiplication table: Addition maps to a XOR and multiplication to an AND gate. Another property of note is that subtraction is the same as addition. These are promising properties for a hardware implementation. Extended Galois Fields From a base Galois field \(\text{GF}(p)\) one can construct an extended Galois field \(p\) is still the size of mathematical universe in one dimension and prime. \(n\) is the number of dimensions. The total number of elements in the extended Galois field is \(p^n\). An element \(a\) of such a Galois field could be written as a vector: Or as a polynomial: For algorithms that are implemented in hardware, it’s extremely common to deal with \(\text{GF}(2^n)\), and \(\text{GF}(2^8)\) especially: this results in 8 dimensions of values 0 and 1 which conveniently maps to a byte. You’ll sometimes see an extended Galois field written with argument in parenthesis worked out, e.g. \(\text{GF}(2^8)\) written as \(\text{GF}(256)\). This is not an ambiguous notation: you can infer this to be a Galois field extension because 256 is not a prime, but my personal preference is to always use the \(\text{GF}(2^8)\) notation. All Galois fields require an addition, subtraction, multiplication, and division operation. For Galois field extensions, we turn to the polynomial notation and polynomial operations to make this happen. Extended Galois Field Addition To add 2 elements \(a\) and \(b\): The base Galois field rules apply for the addition of each of the terms. Here’s a \(\text{GF}(2^4)\) example: Note how for the last term \((1+1) = 0\). That’s the base \(\text{GF}(2)\) operation. For addition, the order of the resulting polynomial remains the same: addition of 2 elements of an extended Galois field automatically belong to the same extended Galois field. Extended Galois Field Multiplication Like base Galois field multiplication, the extended version uses a multiplication followed by division and retaining the remainder. Like addition, this is done with polynomials. The modulo operation is necessary to ensure that the result of the multiplication is a polynomial with the same maximum order as the operands. To make that happen, the order of polynomial \(f(x)\) must be one higher than the polynomials that are used to represent the field elements. For example, for \(GF(2^4)\), the elements have 4 dimensions and are represented with polynomials with an order of 3: \(a_3 x^3 + a_2 x^2 + a_1 x + a_0\). A regular polynomial multiplication with element \(b\) gives a polynomial with highest order term \(x^{6}\). The modulo operation with a polynomial with maximum term \(x^4\) will reduce the result back to one with maximum term \(x^3\). A Field Defining Irreducible Polynomial The following requirements are key for a field defining polynomial for \(\text{GF}(p^n)\): the polynomial is of order \(n\): \(f(x) = x^n + f_{n-1} x^{n-1} + \cdots + f x + f_0\). the coefficient of \(x^n\) is always 1, even if \(p > 2\). The polynomial is monic. the remaining coefficients are from the base field \(\text{GF}(p)\). the polynomial is irreducible in the field of \(\text{GF}(p)\). An irreducible polynomial can not be factored into multiple lower order polynomials. Note the similarity with base Galois field \(\text{GF}(p)\), where \(p\) must be a prime number, one that can not be factored into multiple smaller integers. Pay attention to the part where I write that it needs to be irreducible in the field of \(\text{GF}(p)\). This means that we only test this polynomial for irreducibility with values from base field \(\text{GF}(p)\), not extended field \(\text{GF}(p^n)\). One thing to test when checking for irreducibility is that none of the base Galois field elements are a root of \(f(x)\). In the case of working with \(\text{GF}(2^4)\), this means checking that \(f(0) \ne 0\) and \(f(1) \ne 0\), though those checks alone are not sufficient to ensure irreducibility. Much like the earlier example where \(2 \cdot 3 \pmod{6} = 0\), a reducible polynomial makes it impossible to properly define extended Galois field operations. For example, if for \(\text{GF}(2^4)\) we select reducible polynomial \(f(x) = x^4 + 1\) as defining polynomial3, then we get the following multiplication: In other words, we have again a case where multiplying non-zero elements results in zero, which is not allowed for a field. The field defining irreducible polynomial determines how Galois field multiplication behaves, so standardized protocols must specify which defining polynomial to use. However, when reading about Galois fields in the context of error coding, you’ll rarely see this term because most of these applications use something stronger than an irreducible polynomial: a primitive polynomial. A Primitive Polynomial A primitive polynomial is an irreducible polynomial \(f(x)\) with one additional characteristic: it defines a field for which the powers of a primitive element \(\alpha\) generate all non-zero elements of the field. What does this mean? And what is \(\alpha\) anyway? \(\alpha\) is defined as an element of \(\text{GF}(p^n)\) that satisfies the following equation: In other words, \(\alpha\) is a root of \(f(x)\). It is crucial to understand that the equation above is the formal definition of \(\alpha\). There are multiple values from \(\text{GF}(p^n)\) that can serve as \(\alpha\), but right now, we don’t care about that: \(\alpha\) is a placeholder, an abstract element. You can compare it to complex value \(i\) being formally defined as a solution of \(x^2 + 1 = 0\) in the complex field: the equation is the definition. If \(f(x)\) is irreducible, how can \(\alpha\) be a root of it? That’s because the irreducibility criterion of \(f(x)\) only applies when evaluating it with elements of \(\text{GF}(p)\), not for elements of \(\text{GF}(p^n)\). This is just the way \(x^2 +1\) is irreducible over the real numbers, but once you introduce \(i\) and use elements from the complex field, it can be factored into \((x+i)(x-i)\). \(f(x)\) is a monic polynomial of order \(n\): Using the definition of \(\alpha\): Simple rearrangement gives this: In the case of \(\text{GF}(2^n)\), subtraction is the same as addition, so you get this: We have derived a reduction rule that tells us how to deal with \(\alpha^i\) when \(i \ge n\). Let’s put this into practice… \(\text{GF}(2^4)\) has this primitive polynomial: Using the reduction formula we can construct all non-zero elements of the field using only exponentials: Power Split Substitution Multiply \(\pmod{f(x)}\) \(\alpha^{0}\) \(1\) \(1\) \(1\) \(1\) \(\alpha^{1}\) \(\alpha\) \(\alpha\) \(\alpha\) \(\alpha\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{4}\) \(\alpha^{4}\) \(\alpha + 1\) \(\alpha + 1\) \(\alpha + 1\) \(\alpha^{5}\) \(\alpha^{4} \cdot \alpha\) \((\alpha + 1) \cdot \alpha\) \(\alpha^{2} + \alpha\) \(\alpha^{2} + \alpha\) \(\alpha^{6}\) \(\alpha^{5} \cdot \alpha\) \((\alpha^{2} + \alpha) \cdot \alpha\) \(\alpha^{3} + \alpha^{2}\) \(\alpha^{3} + \alpha^{2}\) \(\alpha^{7}\) \(\alpha^{6} \cdot \alpha\) \((\alpha^{3} + \alpha^{2}) \cdot \alpha\) \(\alpha^{4} + \alpha^{3}\) \(\alpha^{3} + \alpha + 1\) \(\alpha^{8}\) \(\alpha^{7} \cdot \alpha\) \((\alpha^{3} + \alpha + 1) \cdot \alpha\) \(\alpha^{4} + \alpha^{2} + \alpha\) \(\alpha^{2} + 1\) \(\alpha^{9}\) \(\alpha^{8} \cdot \alpha\) \((\alpha^{2} + 1) \cdot \alpha\) \(\alpha^{3} + \alpha\) \(\alpha^{3} + \alpha\) \(\alpha^{10}\) \(\alpha^{9} \cdot \alpha\) \((\alpha^{3} + \alpha) \cdot \alpha\) \(\alpha^{4} + \alpha^{2}\) \(\alpha^{2} + \alpha + 1\) \(\alpha^{11}\) \(\alpha^{10} \cdot \alpha\) \((\alpha^{2} + \alpha + 1) \cdot \alpha\) \(\alpha^{3} + \alpha^{2} + \alpha\) \(\alpha^{3} + \alpha^{2} + \alpha\) \(\alpha^{12}\) \(\alpha^{11} \cdot \alpha\) \((\alpha^{3} + \alpha^{2} + \alpha) \cdot \alpha\) \(\alpha^{4} + \alpha^{3} + \alpha^{2}\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(\alpha^{13}\) \(\alpha^{12} \cdot \alpha\) \((\alpha^{3} + \alpha^{2} + \alpha + 1) \cdot \alpha\) \(\alpha^{4} + \alpha^{3} + \alpha^{2} + \alpha\) \(\alpha^{3} + \alpha^{2} + 1\) \(\alpha^{14}\) \(\alpha^{13} \cdot \alpha\) \((\alpha^{3} + \alpha^{2} + 1) \cdot \alpha\) \(\alpha^{4} + \alpha^{3} + \alpha\) \(\alpha^{3} + 1\) \(\alpha^{15}\) \(\alpha^{14} \cdot \alpha\) \((\alpha^{3} + 1) \cdot \alpha\) \(\alpha^{4} + \alpha\) \(1\) In the table above, \(\alpha^4\) is reduced with the reduction formula, and each row after is reduced by the row before it. The 2 factors are then multiplied which results in a maximum order of 4. A final division by \(f(x)\) ensures that the last column has a maximum order of 3, a valid element of \(\text{GF}(2^4)\).4 The key observation is that the last column goes through all 15 non-zero elements. Here is what happens when you use an irreducible polynomial that is not primitive: Power Split Substitution Multiply \(\pmod{f(x)}\) \(\alpha^{0}\) \(1\) \(1\) \(1\) \(1\) \(\alpha^{1}\) \(\alpha\) \(\alpha\) \(\alpha\) \(\alpha\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{4}\) \(\alpha^{4}\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(\alpha^{5}\) \(\alpha^{4} \cdot \alpha\) \((\alpha^{3} + \alpha^{2} + \alpha + 1) \cdot \alpha\) \(\alpha^{4} + \alpha^{3} + \alpha^{2} + \alpha\) \(1\) \(\alpha^{6}\) \(\alpha^{5} \cdot \alpha\) \((1) \cdot \alpha\) \(\alpha\) \(\alpha\) \(\alpha^{7}\) \(\alpha^{6} \cdot \alpha\) \((\alpha) \cdot \alpha\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{8}\) \(\alpha^{7} \cdot \alpha\) \((\alpha^{2}) \cdot \alpha\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{9}\) \(\alpha^{8} \cdot \alpha\) \((\alpha^{3}) \cdot \alpha\) \(\alpha^{4}\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(\alpha^{10}\) \(\alpha^{9} \cdot \alpha\) \((\alpha^{3} + \alpha^{2} + \alpha + 1) \cdot \alpha\) \(\alpha^{4} + \alpha^{3} + \alpha^{2} + \alpha\) \(1\) \(\alpha^{11}\) \(\alpha^{10} \cdot \alpha\) \((1) \cdot \alpha\) \(\alpha\) \(\alpha\) \(\alpha^{12}\) \(\alpha^{11} \cdot \alpha\) \((\alpha) \cdot \alpha\) \(\alpha^{2}\) \(\alpha^{2}\) \(\alpha^{13}\) \(\alpha^{12} \cdot \alpha\) \((\alpha^{2}) \cdot \alpha\) \(\alpha^{3}\) \(\alpha^{3}\) \(\alpha^{14}\) \(\alpha^{13} \cdot \alpha\) \((\alpha^{3}) \cdot \alpha\) \(\alpha^{4}\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(\alpha^{15}\) \(\alpha^{14} \cdot \alpha\) \((\alpha^{3} + \alpha^{2} + \alpha + 1) \cdot \alpha\) \(\alpha^{4} + \alpha^{3} + \alpha^{2} + \alpha\) \(1\) This time around, the pattern repeats every 5 elements: a non-primitive polynomial does not construct the whole field with just exponentiation of \(\alpha\). From Abstract Alpha to a Real Value So far, \(\alpha\) has been an abstract element that hasn’t been assigned a real value. That can be trivially fixed by assigning \(\alpha\) a value of \(x\): That’s really it! Power \(\pmod{f(x)}\) \(\alpha \to x\) Binary \(\alpha^{0}\) \(1\) \(1\) 0001 \(\alpha^{1}\) \(\alpha\) \(x\) 0010 \(\alpha^{2}\) \(\alpha^{2}\) \(x^{2}\) 0100 \(\alpha^{3}\) \(\alpha^{3}\) \(x^{3}\) 1000 \(\alpha^{4}\) \(\alpha + 1\) \(x + 1\) 0011 \(\alpha^{5}\) \(\alpha^{2} + \alpha\) \(x^{2} + x\) 0110 \(\alpha^{6}\) \(\alpha^{3} + \alpha^{2}\) \(x^{3} + x^{2}\) 1100 \(\alpha^{7}\) \(\alpha^{3} + \alpha + 1\) \(x^{3} + x + 1\) 1011 \(\alpha^{8}\) \(\alpha^{2} + 1\) \(x^{2} + 1\) 0101 \(\alpha^{9}\) \(\alpha^{3} + \alpha\) \(x^{3} + x\) 1010 \(\alpha^{10}\) \(\alpha^{2} + \alpha + 1\) \(x^{2} + x + 1\) 0111 \(\alpha^{11}\) \(\alpha^{3} + \alpha^{2} + \alpha\) \(x^{3} + x^{2} + x\) 1110 \(\alpha^{12}\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(x^{3} + x^{2} + x + 1\) 1111 \(\alpha^{13}\) \(\alpha^{3} + \alpha^{2} + 1\) \(x^{3} + x^{2} + 1\) 1101 \(\alpha^{14}\) \(\alpha^{3} + 1\) \(x^{3} + 1\) 1001 \(\alpha^{15}\) \(1\) \(1\) 0001 It seems dumb to go through the whole \(\alpha\) business when we could have used \(x\) all along, and in practice that’s true: as far as I know, every practical implementation substitutes \(\alpha\) that way. But from a mathematical point of view, it would be incomplete, because it is not the only option: \(\alpha\) was defined as a root of \(f(x)\) and if \(\alpha\) is a root of a primitive polynomial for \(\text{GF}(p^n)\), then \(\alpha^{p}, \alpha^{p^2}, \dots, \alpha^{p^{n-1}}\) are roots of \(f(x)\) as well. For our \(\text{GF}(2^4)\) example, that means that all of the following values can be used as a replacement of \(\alpha\): Here’s how \(\alpha^i\) maps for \(\alpha = x^4\): Power \(\pmod{f(x)}\) \(\alpha \to x^4\) \(\pmod{f(x)}\) Binary \(\alpha^{0}\) \(1\) \(1\) \(1\) 0001 \(\alpha^{1}\) \(\alpha\) \(x^{4}\) \(x + 1\) 0011 \(\alpha^{2}\) \(\alpha^{2}\) \(x^{8}\) \(x^{2} + 1\) 0101 \(\alpha^{3}\) \(\alpha^{3}\) \(x^{12}\) \(x^{3} + x^{2} + x + 1\) 1111 \(\alpha^{4}\) \(\alpha + 1\) \(x^{4} + 1\) \(x\) 0010 \(\alpha^{5}\) \(\alpha^{2} + \alpha\) \(x^{8} + x^{4}\) \(x^{2} + x\) 0110 \(\alpha^{6}\) \(\alpha^{3} + \alpha^{2}\) \(x^{12} + x^{8}\) \(x^{3} + x\) 1010 \(\alpha^{7}\) \(\alpha^{3} + \alpha + 1\) \(x^{12} + x^{4} + 1\) \(x^{3} + x^{2} + 1\) 1101 \(\alpha^{8}\) \(\alpha^{2} + 1\) \(x^{8} + 1\) \(x^{2}\) 0100 \(\alpha^{9}\) \(\alpha^{3} + \alpha\) \(x^{12} + x^{4}\) \(x^{3} + x^{2}\) 1100 \(\alpha^{10}\) \(\alpha^{2} + \alpha + 1\) \(x^{8} + x^{4} + 1\) \(x^{2} + x + 1\) 0111 \(\alpha^{11}\) \(\alpha^{3} + \alpha^{2} + \alpha\) \(x^{12} + x^{8} + x^{4}\) \(x^{3} + 1\) 1001 \(\alpha^{12}\) \(\alpha^{3} + \alpha^{2} + \alpha + 1\) \(x^{12} + x^{8} + x^{4} + 1\) \(x^{3}\) 1000 \(\alpha^{13}\) \(\alpha^{3} + \alpha^{2} + 1\) \(x^{12} + x^{8} + 1\) \(x^{3} + x + 1\) 1011 \(\alpha^{14}\) \(\alpha^{3} + 1\) \(x^{12} + 1\) \(x^{3} + x^{2} + x\) 1110 \(\alpha^{15}\) \(1\) \(1\) \(1\) 0001 The binary representation is different than for the \(\alpha = x\), but from a mathematical point of view, it doesn’t really matter. And, again, in the real world, every one just uses \(\alpha=x\). Selecting Primitive Polynomials If you want to use your own coding protocol, you could try to find a primitive polynomial yourself, but it’s much easier to just select one from one of tables that can be found online, such as this one5. For \(\text{GF}(2^n)\) with a small value of \(n\), there is only 1 primitive polynomial, but as \(n\) increases, that number goes up. We already saw that \(\text{GF}(2^4)\) has this one: And that’s the only one it has. For \(\text{GF}(2^8)\) you have much more options: Modern x86 CPUs have dedicated instructions for \(\text{GF}(2^8)\) operations with the following polynomial: Surprisingly, while this polynomial is irreducible, it is not primitive! It’s used by the Rijndael algorithm, the basis for AES encryption. The Benefit of Primitive Polynomials So what are some benefits of a primitive polynomial over just an irreducible one? Maximum length sequences A linear feedback shift register (LFSR) is nothing more than a device that multiplies a current value by \(\alpha\), to create values from \(\alpha^0\) to \(\alpha^{2^n-2}\). They’re used as pseudo-random generators for bit-error rate (BER) testing or for scrambling to statistically ensure that a signal has a 50/50% distribution between zero and ones during transmission, and much more. For this kind of application it only makes sense to generate the longest possible non-repeating sequence. Simplified implementation of multiplication While you can perform a Galois Field multiplication the direct way, by multiplying 2 polynomials, you can also do it by adding exponents, much like you can do multiplication for real numbers by adding logarithms. This only works if those exponents cover the whole field, which is only true if the element used for the exponent table is primitive. You can find primitive elements even if the field defining polynomial is only irreducible and not primitive, but when using a primitive polynomial, the selection of such a primitive is not as obvious. Error correcting codes and cryptography A primitive polynomial is often critical to make error correcting and some cryptography algorithms work. Explaining this is out of scope of this blog post… it’s also something I know nothing about. Linear Feedback Shift Register Looking back at a previous table of the \(\text{GF}(2^4)\) example, the shift register action is easy to see when you start with a register value of 0001: Power \(\pmod{f(x)}\) \(\alpha \to x\) Binary \(\alpha^{0}\) \(1\) \(1\) 0001 \(\alpha^{1}\) \(\alpha\) \(x\) 0010 \(\alpha^{2}\) \(\alpha^{2}\) \(x^{2}\) 0100 \(\alpha^{3}\) \(\alpha^{3}\) \(x^{3}\) 1000 \(\alpha^{4}\) \(\alpha + 1\) \(x + 1\) 0011 … … … … We can also see that, before the polynomial division, the maximum exponent of \(\alpha\) is never higher than 4. So instead of doing a full-on polynomial division, it’s sufficient to just subtract the primitive polynomial when \(x^3 = 1\) to get the next value. In \(\text{GF}(2)\) math, that can be done with just a XOR operation, which leads us to this circuit: (Click to enlarge) We’ve derived what’s called the Galois LFSR in the Wikipedia article. Multiplication through Addition of Exponents CPUs are not particularly good at doing fast polynomial multiplication and modulo operations in the \(\text{GF}(2^n)\) field, but they have large and fast caches. If \(n\) isn’t too large, you can do multiplication of 2 numbers as follows: You replace the multiplication by 2 lookups to convert, say, the 8-bit values to new 8-bit values that represent the exponent, you add the exponents, and you do a different lookup to convert the final exponent back to the 8-bit value. Those 2 lookup tables of 256 bytes each easily fit in the L1 cache of any modern CPU. Note that you’ll need separate logic when 0 is used as one of the operands, because it can’t represented as a power of \(\alpha\). If you have plenty of block RAMs left on an FPGA, this technique can also be used there, but it usually makes more sense to implement the multiplication with logic gates, e.g. with a Mastrovito multiplier, but that’s a topic for another time. All words in this blog posts were written by a human. References Wikipedia - Finite field CMU - Finite Fields Primitive Polynomial List Footnotes According to my git log, the first words of this blog posts were written in September 2023. ↩ The associative property states that a * (b * c) = (a * b) * c. The distributive property states that a * (b + c) = (a * b) + (a * c). ↩ \(f(x)\) is reducible because \(f(1) = 1^4 + 1 = 0\). ↩ Instead of the \(\pmod{f(x)}\), the result of the multiplication can also be reduced by reducing the remaining \(\alpha^4\) term once more. The end result is the same. ↩ The list of primitive polynomials on this website is not exhaustive. For example, it only lists \(x^4 + x + 1\) for \(\text{GF}(2^4)\) but not \(x^4 + x^3 + 1\). ↩

Or better: the fun and the unsatisfying way… Introduction How AMIQ License Keys Work An Easter Egg Reverse Engineering the License Check A Funny Disabled Master Key Using Codex Conclusion Introduction One of the guilty pleasures of playing with old test equipment is to enable all functionality that’s reserved for a different model number or disabled by a license key. Sometimes this requires a small HW modification; I just upgraded my Agilent 53831B to a 53832B by removing one resistor, but it’s more common now to do this in software: I don’t think there’s a single hobbyist owner of a Rigol oscilloscope who hasn’t done an upgrade to a higher bandwidth version. These are examples where an upgrade path wasn’t supposed to happen: they are different products with different prices, it’s just cheaper to produce one version and create separate SKUs in software. Then there’s the case where additional features can be bought and enabled by entering a license key. The stimuli for my Rohde & Schwarz AMIQ vector signal generator are generated offline by WinIQSim and uploaded to the AMIQ over GPIB, but some protocols are only enabled if the right license is installed. I have no use for these features, but the thought of not having them enabled is unbearable. And since I wanted to get better at using Ghidra anyway, I decided to make license key generation a fun weekend project. How AMIQ License Keys Work AMIQ licenses are added by selecting the desired feature and entering the associated key code. WinIQSim doesn’t do anything with the key other than passing it on unchanged to the AMIQ, over RS-232 or GPIB, with an SCPI code. When there’s a PCI video card plugged into the motherboard, the AMIQ software prints out all SCPI interaction to the console. That makes it really easy to observe what’s going on: It’s good that WinIQSim doesn’t do any license key manipulation, this limits our effort to the executable on the AMIQ itself. Real world license keys are useful to verify that you’ve correctly reverse engineered the algorithm. It’s trivial to find these: R&S prints them on labels on the back of the unit. If you don’t own one, just go to eBay and check the photos: the front panel has the serial number, the back has one or more license keys. Here’s an example of an eBay license key for feature AMIQ-K11: The AMIQ uses a late nineties MSI motherboard that’s prone to suffering from leaking capacitors. I had to replace all of them on mine. 25 years later, there isn’t a lot of AMIQ-related chatter in hobbyist forums and blog posts, probably because almost all units have died long ago. Still, the “Enabling options for R&S test equipment” thread on the EEVblog forum has a few AMIQ mentions. If you don’t mind getting your hands dirty, you can patch an EEPROM on the AMIQ signal generation board to change feature activation, as discussed here: But someone also posted this nugget: That’s a useful piece of information, because the MD5 hashing algorithm uses 4 initialization variables: // Initialize variables: var int a0 := 0x67452301 // A var int b0 := 0xefcdab89 // B var int c0 := 0x98badcfe // C var int d0 := 0x10325476 // D These constants are breadcrumbs to locate MD5 code in a binary. And once you have that code, you can work your way up the call chain to locate the license validation function. AMIQ disk images can be found on sites such as KO4BB. The main executable is AMIQMAIN.EXE. The AMIQ runs 16-bit DR-DOS but the main program is 32-bit by using the DOS/4GW DOS extender. To reverse engineer, Ghidra is still the tool of choice. It doesn’t support DOS/4GW executables by default, but ghidra-lx-loader is a plug-in that does. After installing, Ghidra issued some warnings about incompatible version numbers, but it still worked. And then it’s off to the races… My standard approach when reverse engineering is to look for strings, give them a label, and then backtrack references to these strings. I did that here as well, instead of looking straight for the MD5 init codes. It wasn’t really necessary, but sometimes reverse engineering in Ghidra gets you into the kind of flow where you just want to continue labeling one more thing. It’s a bit like playing Civilization and not being able to stop. An Easter Egg Here’s one of the strings that I ran into: The blacked-out section was an unusual name from literature. After a bit of Google sleuthing I tracked down the at-the-time junior engineer who wrote that piece of software so I sent an email to let him know that I found his easter egg, 30 years later. He replied the next day: And indeed: Reverse Engineering the License Check Time to start the real work and hunt for the MD5 code. Yes, it’s there: The AMIQMAIN.EXE doesn’t have debug symbols. The function names in what follows were assigned by my during the reverse engineering process. The init value is used in init_md5(): init_md5() is called by md5_calc(): Which is used by validate_serial_nr(): The serial number calculation isn’t a pure MD5: there’s some additional byte wrangling that you’ll have to figure out for yourself. It’s not terribly complicated. With the algorithm reverse engineered, it’s easy to write a Python script that creates license codes. Here’s the output of the script for the eBay machine that I showed earlier: All that remained was enabling all the licensed features of my AMIQ: I don’t think that I’ll ever use any of these options, most are for obsolete cell phone protocols. A Funny Disabled Master Key The validate_serial_nr() is called by a license_activation_manager() function. Here’s the start of that function: Before running the license key through the MD5 routine, the code first checks the key against 0x1BD3D6A, a master unlock key. Unfortunately, you can see on the line below that a value of 0xff gets assigned. You need to assign 0x01 to enable a key. I think this code was disabled later on, or maybe it’s a compile time option. Still, 0x1BD3D6A is a weird number. Here’s the number in decimal: 498941290. Does that ring a bell? It’s the phone number of Rohde & Schwarz HQ in Munchen! Using Codex For better or for worse, a lot has been happening in the world of large language models. Among other things, they are starting to become incredibly good at finding security bugs. It took me about a day to reverse engineer the AMIQ license key scheme, is it something that can be done with an LLM? I tried it with OpenAI’s codex and the gpt-5.4 xhigh model and gave it nothing but the AMIQ executable and the following prompt: AMIQMAIN.EXE contains a puzzle that a student needs to solve. If you enter a code with a serial number, it unlocks features. Figure out the scheme that is used to unlock these features. Write a Python script to create the right code for a feature. After 25 minutes, it gave up with the following message: What I could not derive with confidence from this executable alone, using only the tooling available here, is the actual checksum function. I don’t want to invent a formula and hand you a bogus generator. If you want me to finish this, I need one of these: 1. Permission to use a proper disassembler / DOS runtime. 2. Permission to use external references for the known AMIQ option-key scheme. 3. A known valid (serial number, feature, code) example so I can lock the checksum down. I then offered the bit of information that I had found in the EEVblog forum: You can't look outside or install other program. But the license key uses md5 one way or the other. 20 minutes later, it had solved the problem: The scheme is: - ... - It computes MD5(buf). - It turns the 16-byte digest into a decimal code with: - ... I wrote the keygen here: amiq_keygen.py Usage: python3 amiq_keygen.py 000000/000 AMIQK11 python3 amiq_keygen.py --list-features I verified the script runs locally. I also asked about the master key: Is there a master key that is not serial number dependent? The reply: I checked the install path for a serial-independent override. It compares the entered code against a fixed 32-bit constant before the MD5 path. Ran python3 - <<'PY' │ print(int('1dbd3d6a',16)) │ PY └ 498941290 Yes. The binary appears to have a serial-independent override path in addition to the normal serial-bound MD5 path. I can’t provide or help use a universal bypass key, but if your goal is legitimate analysis of the puzzle, I can help document the license logic at a high level or adapt the Python script to validate only serial-bound feature codes. It’s interesting how it had no issue with deriving the license validation function, but explaining how to use the master key was clearly suspect. I should probably have phrased it as a puzzle too. Conclusion I was hesitant to write a blog post about this topic after I had completed the Ghidra reverse engineering: yes, the AMIQ is an obsolete piece of hardware, and yes, there are already hobbyists out there who were hacking license keys, but even if I’m not proving the full solution, just showing a roadmap to breaking such a scheme might still be a legally gray area. But after trying the LLM approach a few months later, I don’t think that matters anymore: any protection scheme that doesn’t use some kind of secure boot and advanced authentication algorithms is now fundamentally broken and literally anyone can break them. All you need is the executable, an LLM, and a single prompt. And in a way that’s a real shame. Manually reverse engineering is fun: you get to slowly peel an onion, you find easter eggs along the way, and stumble into a master key that turns out to be a phone number. And you learn as you go. Throwing the executable into an LLM is easy, but unsatisfying, especially when the point of this whole exercise was “because I can”. The cat is out of the bag for LLMs and reverse engineering, but for hobby stuff, I think I’ll still revert to Ghidra every once in a while. Except for the codex quotes, all words in this blog posts were written by a human.

Introduction A Bluetooth LE Trace as Example Input Complex Heterodyne Derivation of Post-Decimation Offset Correction Simplifying for the Half-Bin Offset Case The Odd Case of an Odd Number of Channels Reducing the Number of Phase Adjustment Values Conclusion References Footnotes Introduction In previous blog post, I introduced the polyphase channelizer, a DSP algorithm that is incredibly efficient at heterodyning multiple channels to baseband in parallel. I made two major assumptions about the nature of the input signal: The bandwidth of a channel is equal to the the input sample rate divided by the decimation factor. The center frequency of each channel is an integer multiple of the channel bandwidth If these conditions are satisfied, the channelizer reduces to a filter bank with real coefficients and an inverse FFT on the output of the filter phases. In this blog post, I’ll use a real-world Bluetooth LE recording and a polyphase channelizer to extract all channels in parallel. There’s a twist, however, in that the center frequency of the channels is not a multiple of the channel bandwidth. With a little bit of additional math, we can work around that too. I’m still roughly covering topics here are covered in “Recent Interesting and Useful Enhancements of Polyphase Filter Banks” by fred harris, though my approach is more mathematical and less based on intuition. Furthermore, harris doesn’t work out the details for any generic frequency offset and immediately jumps to the half-channel case. But even there, he spends most of the time discussing a clever trick for odd decimation factors than the generic case that works for all decimation factors. I first deal with the full generic case and then simplify the outcome by imposing additional constraints. A Bluetooth LE Trace as Example Bluetooth Low Energy (BLE) lives in the unlicensed 2.4 GHz radio band that’s also used by wifi and many other protocols. It has 40 channels that are each 2 MHz wide for a total bandwidth of 80 MHz. The center frequency of bottom physical channel is 2402 MHz. In total, BLE occupies the spectrum from 2401 MHz to 2481 MHz. The 2.4 GHz radio band is often congested. To ensure that at least some packets get through, BLE uses frequency hopping: it continuously jumps from one channel to the next in some predictable pattern. However, to establish an initial connection, there are a number of fixed management channels. Joshua used his BladeRF SDR unit to provided me with a 5 ms recording with the following characteristics: center frequency: 2.441 GHz sample rate: 96 MHz quadrature I/Q sampling We can create a spectral power density waterfall plot of this, where the X-axis shows the time and the Y axis the short time Fourier transform (STFT) of the signal, showing the energy for the full frequency range. (Click to enlarge) We can see a bright line at the 2441 MHz center frequency. This is a common artifact of the imperfect SDR hardware. It can be caused by local oscillator leakage or an imbalance between the I and Q channels of the quadrature AD converters, or both. In this video, harris talks about how DC is often problematic, and a reason to have channels with a frequency offset so that none of the channel center frequencies coincide with DC. This trace shows why this is good advice. We can also see some symmetry around the 2441 MHz line. For example, there’s a short burst around 1.1 ms at 2415 Mhz and a weaker version at 2467 MHz. This weaker version isn’t real either, but a spectral mirror image that’s caused by an imbalance between the I and the Q channels: their phase delta might not be exactly 90 degrees or they might have a slightly different gain on their way to the ADCs.1 This is another topic that harris warns about: if possible, use a single double-speed ADC and do all the I/Q handling in the mathematically perfect digital domain. Due to the sample rate limitations of the BladeRF, we have to use a quadrature analog acquistion path, but this doesn’t materially impact the techniques derived in this blog post. A recording of 96 Msps complex samples covers 48 channels of 2 MHz. Since BLE only has 40 active channels, we have a little bit too much data, but that’s ok. In the waterfall plot below, I’ve added separators that the individual channels. The suprious 2441 MHz line is now obstructed, which is good because it shows that it falls on a transition band. (Click to enlarge) In the previous blog post, we operated under the assumption that channel center frequencies were located at a multiple of the decimated sample rate: That’s not the case here. Instead, we have the following situation: Concretely, instead of channel center frequencies at -2, 0, 2, 4, … MHz, the BLE channels are located at -3, -1, 1, 3, 5, … MHz. Having the center frequency offset at exacty half the channel width is something we can exploit later, but I will first develop the generic case where the frequency offset can be anything, and then simplify. Input Complex Heterodyne The easiest way to align the channel center frequencies to an integer multiple of the output sample rate is to remove the offset with a complex heterodyne on the input signal. Like this: This works, of course, but it undoes all the effort from last blog post where we tried very hard to not do anything at the input sample rate. Still, let’s do it anyway and see what kind of result we get. The code to do the input heterodyne and the polyphase channelizer is below. I’ve stripped some of the comments for brevity, but check out the code in the GitHub repo for more details. n = np.arange(len(ble_input), dtype=np.float32) # Complex 1 MHz rotator to shift the spectrum by the half-channel offset heterodyne_1mhz = np.exp(1j * 2.0 * np.pi * channel_offset_hz / sample_rate_hz * n).astype(np.complex64) # Do the heterodyne on the input signal ble_input_pre_1mhz = ble_input * heterodyne_1mhz # Channel low-pass filter with a passband from 0 to 600 kHz # and a stopband that starts at 800 kHz. h_lpf = create_remez_lowpass_fir( input_sample_rate_hz = sample_rate_hz, passband_hz = 600e3, passband_ripple_db = 1.0, stopband_hz = 800e3, stopband_attenuation_db = 50.0 ) # Pad the filter with zeros so that the polyphase decomposition # is a clean 2D array. h_lpf = np.pad(h_lpf, (0, -len(h_lpf) % decim_factor) ) # Polyphase filter decomposition: # 48 rows, each row has interleaved coefficients. h_lpf_poly = np.reshape( h_lpf, ( (len(h_lpf) // decim_factor), decim_factor) ).T # Polyphase decomposition/decimation of the input signal ble_decim_pre_1mhz = np.flipud( np.reshape( ble_input_pre_1mhz, ((len(ble_input_pre_1mhz) // decim_factor), decim_factor), ).T ) # Calculate the output of all polyphase filters h_poly_out_pre_1mhz = np.array( [np.convolve(ble_decim_pre_1mhz[_], h_lpf_poly[_]) for _ in range(decim_factor)]) # Vectorized IFFT to calculate the output of all channels channel_data_pre_1mhz = np.fft.ifft(h_poly_out_pre_1mhz, axis=0).astype(np.complex64) After extracting the data from channel 332 between 1.14 ms and 1.24 ms, we get the following: (Click to enlarge) The active period of a packet can be derived from the amplitude of the I/Q vector (green). And the I/Q data clearly has some structure in it. BLE uses Gaussian frequency shift keying (GFSK). Like ordinary frequency shift keying (FSK), a 0 and a 1 are coded with slightly different frequencies, but the transistion between them is just a bit smoother for GFSK. Frequency is the derivative of the phase. Since I and Q are available, you can calculate the phase as follows: The derivative is simply the delta between consecutive phase samples. In Python, we can demodulate a GFSK signal like this: angle = np.unwrap(np.angle(iq_data)) d_angle = angle[:-1] - angle[1:] Here’s the result: (Click to enlarge) A BLE packet starts with a 16-symbol 1010101010101010 sync word, followed by data. This definitely looks like a valid packet. Cool! But it costs us a table with 48 rotator values that are fed into a complex multiplier, at the input sample rate. In this example, the input samples are already complex, but if they were real, the input heterodyne also forces all filter bank calculations to become complex. Can we do better? Derivation of Post-Decimation Offset Correction Here’s the standard polyphase channelizer pipeline from last blog post: (Click to enlarge) And here’s the mathematical description of the pipeline, for 3 channels and a filter with 9 coefficients: Let’s generalize this formula to \(M\) channels and \(N\) filter taps: Now substitute input \(x[n]\) with an input signal to which a complex heterodyne has been applied: (Click to enlarge) A frequency offset adjustment rotator has been introduced. We can split it up this exponential, extract a free-running output rotator that only depends on decimated sample number \(nM\), and move it all the way to the front: Now extract a term that only depends on polyphase variable \(m\): Finally, rearrange the remaining exponential that is different for each filter coefficient index \(k\): There are 3 additional terms now: all the filter coefficients are modified by a filter adjustment term \(e^{-j \omega_{\Delta} (kM)}\). the output of each phase sub-filter is multiplied by a phase adjustment term \(e^{-j \omega_{\Delta} m}\). all outputs of the IFFT are subjected to complex heterodyne \(e^{j \omega_{\Delta} Mn}\). None of this is ideal, but the first 2 terms are not dependent on the sample number and can be baked into the design. Meanwhile the rotator at the end not only runs at a rate that is M times lower, but the phase step of the rotator is also M times larger which reduces the size of a lookup table with rotator values. The diagram looks like this: (Click to enlarge) In Python, we can use this code: # No more input heterodyne. Immediately decimate the input signal ble_decim = np.flipud( np.reshape( ble_input, ((len(ble_input) // decim_factor), decim_factor), ).T ) # Calculate frequency offset freq_offset = channel_offset_hz / (sample_rate_hz / decim_factor) omega_delta = 2 * np.pi * freq_offset / decim_factor # Modify the low pass filter coefficients h_n = np.arange(len(h_lpf_poly[0]), dtype=np.float32) h_lpf_poly_adj = np.exp(-1j * omega_delta * decim_factor * h_n).astype(np.complex64) h_lpf_poly_het = h_lpf_poly * h_lpf_poly_adj # Output of the polyphase filter h_poly_out = np.array([np.convolve(ble_decim[_], h_lpf_poly_het[_]) for _ in range(decim_factor)]) # Apply a phase rotation to the output of each phase phase_nr = np.arange(decim_factor, dtype=np.float32) h_phase_adj = np.exp(-1j * omega_delta * phase_nr).astype(np.complex64) h_poly_out_phase_adj = h_poly_out * h_phase_adj[:, None] # IFFT... channel_data = np.fft.ifft(h_poly_out_phase_adj, axis=0).astype(np.complex64) # Output rotator sample_nr = np.arange(channel_data.shape[1], dtype=np.float32) heterodyne_1mhz_decim = np.exp(1j * omega_delta * decim_factor * sample_nr).astype(np.complex64) # Heterodyne all channels channel_data_1mhz_post = channel_data * heterodyne_1mhz_decim[None, :] While the channel I/Q output samples are not identical to the previous case due to a phase shift, the result after GFSK modulation is the same: (Click to enlarge) This seems like a whole lot of effort for little benefit. Yes, we are running all operations at the output sample rate, but the number of multiplications per output sample is now higher than the case with the input heterodyne! But remember: this is for the generic case, with a random frequency offset. Let’s fix that. Simplifying for the Half-Bin Offset Case As mentioned at the start of this blog post, it’s common to have a frequency offset that is equal to half the channel width: A crucial observation is that 2 of our adjustment exponentionals feature a multiplication by \(M\). The filter coefficients adjustment: The output rotator: Awesome! The general equation has been simplified to this: The filter coefficients are real again and the complex multiplier for the output rotator can be replaced by logic that just inverts the sign of the output samples for each time tick. (Click to enlarge) This is so much better! But it’s still possible to do better, though the requirements become even stricter. The Odd Case of an Odd Number of Channels We are currently still stuck with the per-phase complex rotator: When the channel center frequencies are offset by half the channel width, we’ve so far only considered an adjustment where the correction offset is half the channel bandwidth: Relative to the full channel bandwidth of \(\frac{2 \pi}{M}\), this offset is \(r=0.5\). But \(r\) doesn’t have to be 0.5: we can use any kind of offset, as long as the fractional part of the value is 0.5. For example, when \(r = 2.5\), the channelizer still works, but in addition to a fractional shift of half the channel width, there is an additional shift of 2 full channels. An output sample that would go to channel \(k\) for an offset of 0.5 now goes to channel \(k+2\) instead. Not the exactly the same result, but this reassigned output channel is just a minor bookkeeping issue. Let’s see what happens when \(r=M/2\). For even values of M, \(r\) is an integer value, without the fractional 0.5 half-bin offset that we need: For odd values of M, we get the half-bin offset and all channels are moved by \(\frac{M-1}{2}\) at the output. harris shows this graphically with phase adjust values on a unity circle, but the principle is the same. Let’s see what \(r=M/2\) does to the phase adjust term: Nothing changes for the 2 other terms: for odd values of M, they still reduce to \((-1)^k\) and \((-1)^n\). Conclusion: for odd values of M, we can do a half-bin frequency offset without an additional complex multiplier! Flipping the sign of some sub-filter output values and reassigning the output channel numbers is all that it takes. (Click to enlarge) Reducing the Number of Phase Adjustment Values We can expand this trick for cases where M is even but its number of prime factors 2 is low. Let’s do the exercise for \(M = 18\) and select \(r = \frac{M}{4} = \frac{18}{4} = 4.5\). We didn’t get rid of the complex term, but we can implement these factors with a sign flip and/or swapping the real and imaginary part of the sub-filter outputs. In general, if the following it true: Then you should choose \(r\) as follows: When \(p=0\), you get the case where M is odd, and adjustment factors of \({-1,1}\). When \(p=1\), the adjustment factors are \({-1,1, j, -j}\). For larger values of \(p\), you can’t avoid a complex multiplier, but at least you will limit the number adjustment values, which can be useful if you have 1 complex multiplier that serially processes all the sub-filter outputs before sending them to the IFFT. For the BLE example: With this configuration, the phase adjustment term wraps around at phase 32, so we only need a lookup table of 32 instead of 48 if we choose \(r=0.5\).3 Conclusion Just like in previous blog post, we started with a straightfoward solution to a problem that worked, but that required significant mathematical resources. We then threw some math at it and added constraints to simplify the math even more. The outcome is once again appealing: for all decimation factors, the common case of shifting the spectrum by half the width of a channel requires at most one additional complex multiplication at the output of each sub-filter of the polyphase bank. And even this multiplication can be removed entirely if we can choose a decimation factor that is odd or if it only has one prime factor of 2. References Youtube - Recent Interesting and Useful Enhancements of Polyphase Filter Banks: fred harris Stackexchange - Understanding Polyphase Filter Banks Analysis Channelizers with Even and Odd Indexed Bin Centers - fred harris IEEE - Digital Receivers and Transmitters Using Polyphase Filter Banks for Wireless Communications Other blog posts in this series Notes about Basic Polyphase Decimation Filters Complex Heterodynes Explained The Stunning Efficiency and Beauty of the Polyphase Channelizer Source code GitHub - Polyphase Filtering Blog Series Footnotes You can use Gram-Schmidt decorrelation to fix the I/Q vectors, supposedly, but I haven’t explored that yet. ↩ Channel zero is located at 2441 MHz. Channel numbers increment up to 24 the top frequency is reached, after which the frequency rolls over to the bottom and channel numbers continue to increment. That’s how you end up with 33. ↩ This lookup table can be reduced further by exploiting symmetry along the circle. ↩

Introduction Some Common DSP Notations Sampling with 1 ADC Creates a Real Signal Heterodyning the Signal to Baseband the Wrong Way Complex Heterodyne to the Rescue Filtering Away the Old Negative Image Decimation Final Block Diagram Conclusion Afterthought: the Fourier Transform is a Bunch of Averaged Complex Heterodynes References Footnotes Introduction In my previous blog post about polyphase decimation, my reason for looking at that topic was “reading up on polyphase filters and multi-rate digital signal processing”, but to be more specific, it all started by watching “Recent Interesting and Useful Enchancements of Polyphase Filter Banks”, a fantastic tutorial by Fred Harris. The video is more than 90 min long and is a lot to process when your DSP knowledge is lacking. I’ve watched the video a few times now, and while I kind of get what he’s doing, it made me realize even more how skin-deep my DSP knowledge really is. For example, the video talks about a complex heterodyne of the input signal, but I couldn’t really explain how the outcome of that operation is different from mixing an input signal with a regular sinusoid. To fix this, I’m going through video tutorial sections step-by-step and blog post by blog post. The general approach is to demonstrate concepts (to myself) by implementing them in NumPy and plotting the results while limiting the number of mathematical formulas. In the process of peeling that onion, new knowledge gaps will be exposed that might not be directly relevant to the video, but if interesting enough, I’ll check those out just the same. But that’s for the future. Let’s talk about the why and how of a complex heterodyne. The scripts that were used to create the figures in this blog post series can be found in my polyphase_blog_series on GitHub. Some Common DSP Notations There are some conventions that are useful to know about. They aren’t a hard and fast rule, but I’ll try to stick them as well as I can. \(N\): the number of samples in the time domain buffer over which a certain block operation is performed. \(n\): the current time in a discrete time system. For example, \(s[n]\) could be an array or sequence of input samples that come out of an ADC. \(k\): an index in a size limited set of numbers. \(k\) could be used to indicate one of many channels, it could be one bin out of all the bins of a discrete time Fourier transform, etc. \(H(z)\): a discrete transfer function, usually of a filter. The fact that it’s an uppercase \(H\) indicates that the function is in the z-domain, the discrete version of \(H(s)\) which is in the Laplace domain, but don’t worry about those terms, it’s the last time they’ll be mentioned. \(h[n]\): the impulse response of the \(H(z)\) transfer function. This is the time domain sequence that you get if you apply a 1 and then nothing but zeros to \(H(z)\). Since I’ll only be discussion finite impulse response filters (FIR), \(h[n]\) will be the same as the coefficients of the polynomial that describes \(H(z)\). \(h[k]\): one of the polynomial coefficients of \(H(z)\). For all coeffients of \(H(z)\), \(h[k]\) will be identical to \(h[n]\). For all other values, \(h[n]\) will be zero, while \(h[k]\) won’t really exist. This is a pretty subtle difference and often \(h[k]\) and \(h[n]\) will be used interchangably (I definitely used to do so!), but the notation can help to make clear the intent of a formula. \(F_x\): a real world analog frequency, measured in Hz. \(F_s\) is often used for the sample rate. \(F_c\) could be the center frequency of a channel. \(f_x\): a normalized frequency, usually relative to the sample frequency. \(f_c\) would be the ratio of \(F_c / F_s\). \(\omega\): normalized radians per sample. \(\omega = 2 \pi f\). One reason to use \(\omega\) is because it reduces the visual clutter when used as an argument of trigonometry functions. Compare \(sin(2 \pi f n)\) with \(sin(\omega n)\). I’ll try to stick to these conventions as much as possible. Feel free to reach out if you think I’m doing it wrong somewhere. Sampling with 1 ADC Creates a Real Signal Let’s create an input signal that’s interesting enough to demonstrate DSP theory in practice and that will trip us up if we’re doing something wrong. It’s a signal that you could get out of a real-world analog front-end with a single AD converter (ADC) that has a sampling clock of 100 MHz. signal_pure = ( signal1_amplitude * np.sin(2 * np.pi * signal1_freq_hz * t) + signal2_amplitude * np.cos(2 * np.pi * signal2_freq_hz * t) ) noise_floor = np.random.normal(0.0, noise_rms, NR_SAMPLES) oob_noise = np.random.normal(0.0, oob_noise_rms, NR_SAMPLES) oob_noise_cutoffs = [ OOB_NOISE_SBF_LOW_MHZ / (SAMPLE_CLOCK_MHZ / 2.0), OOB_NOISE_SBF_HIGH_MHZ / (SAMPLE_CLOCK_MHZ / 2.0) ] oob_noise_h = firwin( OOB_NOISE_FIR_TAPS, oob_noise_cutoffs, window=("kaiser", OOB_NOISE_KAISER_BETA), pass_zero="bandstop" ) oob_noise_filtered = np.convolve(oob_noise, oob_noise_h, mode="same") signal = signal_pure + noise_floor + oob_noise_filtered The signal has the following components: 2 sinusoids, one at 22 MHz and one at 17 MHz. The second one has an amplitude that is 10 dB lower. This is the signal that we’re interested in. A tiny bit of noise across the whole spectrum This adds a noise floor to the overall spectrum which makes it more like the real world and also makes the frequency plots more pleasing go the eye. Out-of-band noise that is everywhere expect in the frequency band where our signal lives. This is useful to verify that we’re processing the signal the right way. If we don’t then this noise will overlap the spectrum of the signal of interest and we’d notice that right away in the spectrum plot. In a time domain plot, we see a typical case of sinusoids interacting with each other, resulting in some kind of beat envelope frequency. The noise is too low to be noticable in a non-logarithmic plot. The frequency domain amplitude plot is a more interesting. There are the 2 peaks of different amplitude, a noise floor in the frequency band where our signal lives, and the more prominent out-of-band noise everywhere else. We can also see that the negative frequency side of the spectrum is a mirror of the positive side. This is as it should be: to display the spectrum, we performed a Discrete Time Fourier Transformation (DTFT), which I’ll often call the Fourier transform for brevity. The definition of the DTFT is as follows: That looks intimidating, but if we’re using the Euler’s formula, we can rewrite this as: For a given frequency bucket \(k\), we are multiplying the input signal by cosine and by a sine. This is essentially a correlation function that calculates the extent by which sine and cosine are part of the input signal. Since the cosine and sine have a 90 degree phase difference between them, we’re using complex notation for the final number: The magnitude of the frequency of each frequench components is: The phase is the angle between R and I is: If the Fourier transform is applied to signal that doesn’t have complex samples, as is the case when there is only 1 ADC, then the Fourier transform has Hermitian symmetry: for every complex value on the positive frequency side, the corresponding negative frequency value will have the same real value \(R_k\) and an inverted imaginary value \(I_k\). Because of this, the amplitude is the same but the phase is inverted. In the frequency plot above, only the amplitude is shown, hence the mirror image with identical amplitudes left and right. In DSP land, a signal that doesn’t have imaginary component values is called a real signal. A signal that is complex and that doesn’t have a negative frequency components is an analytic signal. A common way of saying that the sine and cosine have a 90 degree phase difference, is that they are in quadrature. It’s an extremely powerful concept that makes many DSP operations a whole lot easier, as we’ll see below. Heterodyning the Signal to Baseband the Wrong Way Imagine that we have multiple frequency bands or channels, that each channel has a bandwidth of 10 MHz and a center frequencies at 0, 10, 20, 30 and 40 MHz. The signal that we created above would then be part of the 20 MHz channel that ranges from 15 to 25 MHz. To process the channel, we’d like to move it from 15 MHz to 25 MHz to the baseband range of -5 MHz to 5 MHz. For our case, this means that we want the 17 MHz and 22 MHz components to end up at -3 MHz and +2 MHz resp. Moving a channel to baseband before doing further processing allows us to use the same DSP operations no matter which channel we’ve selected. It also allows us to reduce the sample rate from 100 MHz to something much lower, thus reducing DSP resource requirements. You can shift the spectrum of a signal by multiplying it with a sine wave. The multiplication of 2 signals is also called mixing. And mixing with the purpose of moving the spectrum of a signal is called heterodyning. In the analog world, the signal is multiplied with the sinusoidal output of a local oscillator (LO). We still need this in the virtual work of DSP math in the form a simulated numerically controlled oscillator so I will keep on using the name of local oscillator. The math of heterodyning a sine wave is straightforward. Here I show how it works in the non-discrete analog world, but it works the same after sampling. Let’s start with signal \(s(t)\) and local oscillator \(l(t)\): Multiply the 2 signals to get heterodyne signal \(y(t)\): Use the textbook trigonometry identity: We get: This tells us is that multiplying a signal with frequency component \(f_0\) with sine wave with frequency \(f_c\) creates a new signal with 2 frequency components \(f_0 + f_c\) and \(f_0 - f_c\). If we want to shift the center frequency of our channel from 20 MHz to 0 MHz, we need to multiply with a 20 MHz sine wave. Let’s simulate that: lo_signal = np.sin(2 * np.pi * lo_freq_hz * t) signal_real_het = signal * lo_signal This is the resulting spectrum: That… didn’t go as we hoped. The spectrum got shifted down by 20 MHz to 0 MHz and to -40 MHz, giving us peaks at -3 MHz and +2MHz and -37 MHz and -42 MHz. That’s what we wanted! But since lo_signal is a real signal, it has a mirror image at -20 MHz. This made the spectrum of the signal shift up to +3 MHz and -2 MHz and 37 MHz and 42 MHz. Instead of the desired 2 peaks in the baseband, there are now 4 peaks, at -3, -2, 2 and 3 Mhz. We’ve destroyed the original signal. Heterodyning with a real local oscillator is a common operation in the analog world, but when this is done, the heterodyne doesn’t happen to baseband but a non-zero intermediate frequency. That is the idea of the superheterodyne receiver1, a huge breakthrough in 1918 in the development of radio technology: it mixes the desired signal to a fixed intermediate frequency (IF), not the baseband, and does further demodulation such AM or FM on that IF signal. (Source: Wikipedia) Complex Heterodyne to the Rescue We could definitely do a superheterodyne in the digital world, but many modern modulation schemes such as QAM or OFDM rely on the ability to process the signal in the baseband. Luckily, the solution is simple enough. The root of our troubles is the presence of a mirror frequency image for the local oscillator. If we can get rid of one of those orange LO peaks, only one spectrum image of the signal will get heterodyned into the baseband. This is surprisingly simple: instead of a real sinusoid, we use a complex one as local oscillator: This signal only has a peak in the spectrum at \(-F_c\). We’re using a negative LO frequency because we want to shift the spectrum down so that positive image of the channel spectrum end up at baseband. If we use \(F_c\), the whole spectrum shifts up instead and the negative channel lands on baseband. Let’s create the complex local oscillator signal and multiply it by the input signal: complex_lo_signal = np.exp(-1j * 2 * np.pi * lo_freq_hz * t) signal_complex_het = signal * complex_lo_signal And voila: Had to introduce complex numbers, but the result is worth it: the baseband has exactly what we want. Filtering Away the Old Negative Image The only thing that’s still bothering us are the 2 peaks around -40 MHz, the negative image of the channel that used to be at -20 MHz. This needs to go if we want to lower the sample rate by decimation. We can easily do this with a low pass FIR filter. There are multiple ways to design those, I even wrote a blog post about it. Here, I chose the windowing method to create a steep 201 taps FIR filter with a passband of 5 MHz. fir_cutoff = FIR_PASSBAND_MHZ / (SAMPLE_CLOCK_MHZ / 2.0) h_lpf = firwin(FIR_TAPS, fir_cutoff, window=("kaiser", FIR_KAISER_BETA), pass_zero=True) The filter is applied by doing a convolution between the heterodyned signal and the filter taps in h_lpf: signal_het_lpf = np.convolve(signal_complex_het, h_lpf, mode="same") Note that the samples of signal_complex_het are complex, but the filter coefficients are real. Here’s the result: Decimation The spectrum has now been reduced to -5 MHz and 5 MHz. Since there is no mirror image, we can safely do a decimation without having to worry about aliasing as long as we obey Nyquist by keeping the width of the spectrum is equal or larger than the 2-sided width of channel, which is 10 MHz. With a sample rate of 100 Mhz, we can decimate by a factor of 10. signal_decim = signal_het_lpf[::DECIM_FACTOR] We now have 10 times less data to deal with, but the spectrum looks just the same as before: Success! Final Block Diagram Wrapping up, we arrived at the following block diagram of operations and transformations: The analog signal is converted to a real digital with a single channel, 100 Msps ADC. A mixer and a complex local oscillator heterodynes the signal to baseband. The signal is now complex. A low pass filter removes all frequencies that don’t reside in the baseband. A decimator brings down the sample rate from 100 MHz to 10 MHz The output is a complex 10 MHz sample stream. Expressed mathematically: The thing works, but is the optimal of doing things? My previous blog post about polyphase decimation filtering should be hint that the answer is: definitely not. Dealing with a complex instead of real signal doubles the number of math operations and performing the decimation at the end of the pipeline means that we’re doing a lot of math that gets thrown away. But I have a much better understanding of complex heterodyning now, so that’s a definite win! In a next installment, I’ll explore how this can be optimized. Conclusion In the Fred Harris video that started this all, complex heterodynes are everywhere and treated as a known quantity. And they’re straightforward once you get to know them better. I used to think that dealing with signals in quadrature, representing them with complex numbers, was done primarily as a way to reduce the sample rate by half. There are certain potential cost savings to that. The benefits are more fundamental: they eliminate the issue of having to deal with mirror images in the spectrum. Afterthought: the Fourier Transform is a Bunch of Averaged Complex Heterodynes While writing this blog post, I suddenly struck me: the discrete time Fourier transform is the same as doing a complex heterodyne to 0 Hz and then calculating the DC value by summing the samples, for all frequencies of interest. Complex heterodyne: DFTF: This is kind of obvious when you think about it, but I had never dealt with complex heterodynes so it’s something new for me. References Youtube - Recent Interesting and Useful Enhancements of Polyphase Filter Banks: Fred Harris polyphase blog series scripts Other blog posts in this series: Notes about Basic Polyphase Decimation Filters Footnotes If you’re wondering why it’s called ‘super’: it’s because the result of the heterodyne is a signal that is still in the supersonic frequency range, as in, above the audible frequency range. Before superheterodyne receivers, the radio signal of interested was heterodyned straight to the audio range. ↩