More from joshua stein
Amend 4.0 has been released: amend-4.0.sit (StuffIt 3 archive, includes source code and THINK C 5 project file) c838ee34931c00c03869affe7f9d6b85c0bbc51dd1242d11e8682a3774fdd0e3 SHA1: 040059d0b3302f1bd6ec0207b9a2f12dccdda374 Changes in this version: New repository format that tracks author e-mail in addition to name; existing repositories are migrated automatically on open Add inregrated resource file support; .rsrc files can be added directly to a repo and files are converted to DeRez-style ASCII output before diffing, so running SADerez to produce separate .r files on every change is no longer required Allow Command+. to cancel loading a repo Allow Command+. to cancel diffing; if diff text has already been output it will remain available, otherwise the window will be closed Center settings dialog, make sure author name is present Use database transactions to avoid leaving repository database files in a partially-committed state if we crash Numerous bug fixes
In 2019, I started watching Andreas Kling's programming videos, many of which were live-coding sessions writing his new operating system Serenity OS. He was always pretty fast at writing code, especially since his IDE, Qt Creator, had knowledge of all his C++ code and could auto-complete classes, variable names, and function signatures. Back then it seemed like he had much of the code written in his head and was limited just by his typing speed. Four years later, he switched to CLion which had early GitHub Copilot support for AI-assisted code completion. While initially skeptical of Copilot, he experimented with it and within months, Copilot was writing code blocks, "reading [his] mind", and writing whole functions. His IDE's auto-completion through AI seemed like it had finally caught up with his brain and he could get ideas out into code faster. While I found it fascinating watching Andreas speed up his development, none of it appealed to me for my work for years after. I didn't even use an IDE or an LSP in my editor. I was skeptical of AI and probably wrote it off too soon due to its early failures. I eventually tinkered with Claude in a web browser, asking it questions that I would have otherwise asked a search engine and been directed to a Stack Overflow answer. Once Claude Code came out, I was amazed at the power of giving it access to a directory of code on my laptop and letting it directly read and modify files. Its ability to completely (and quickly) reverse engineer a binary blob with zero context is still pretty awesome. Once local models got good and small enough, I started using Ollama on my M4 Mac Mini to do local offline work. Like many things, it's possible to like and use a technology, language, or tool while rejecting all of the hype, fraud, and negative communities that build up around them (like Rails, or Rust). Of course, you can also choose not to like or use any of those things. You can prefer to use a hand saw instead of a circular saw, or to drive a manual transmission car instead of a self-driving EV. But I think at this point it's naive to think of all AI technology as useless or bad. The AI industry on the other hand… In 2020, taking inspiration from Andreas, I started recording my own videos programming on an 8 Mhz Macintosh 512Ke (later a Macintosh Plus) in the THINK C 5 IDE. I had never actually used a classic Macintosh before and I wanted to learn what it was like to program for them as one would have 40 years ago. I made a rule for myself that I would only write code on the Macintosh itself, typing everything on its Apple M0110 keyboard. No modern computers would be involved in writing, editing, or compiling any of the code for my projects. Since starting that series, I've written (most of) an IMAP e-mail client, a revision control system, a Wikipedia reader, an IRC client, then a multi-user, multi-threaded BBS server. It all taught me a lot about the Macintosh and about C, and ignited my vintage computing hobby which has introduced me to many new friends. One thing about writing my e-mail client that bugged me was that it required a proxy server on a modern server to strip TLS and present plaintext to the poky Macintosh. So after adding Wi-Fi functionality to my Mac Plus, I added a TLS offloading device so my Mac could do TLS decryption independently. That provided the final giant piece of the puzzle needed to write a "modern" web browser (at least something newer than MacWeb that could parse HTML 5) for classic Mac OS, since everything is encrypted these days. I started working on that browser in 2024, adding other protocols such as Gopher (and begrudgingly, Gemini). A couple months ago, I was feeling particularly salty about computers and posted these notes: I have lost all enthusiasm for reading about new software projects, especially dealing with vintage computing. What would have sounded amazing a year or two ago and made me want to engage with the author, I now just assume was something AI spit out and feels hollow and boring so I skim past it. And writing software feels like being Marge in that go-kart race. Work slow and steady for a year writing something neat that had never been brought to a platform before, but someone can hear about it and use Claude to whiz by you in a week and make something with 10 times the functionality. Case in point, I saw these today: A modern web browser for Mac OS 9 with CSS, ES5 JavaScript, and TLS A 3D printer monitoring app for System 7 with video A year ago either would have sounded awesome but now I scroll past because I assume AI wrote it all Today someone posted this, a completely vibe-coded Gopher client for classic Mac OS. Claude even made a fancy website for it. And wouldn't you know it, but some of the code for it even comes from my own projects. The other week, Andreas tweeted this: Feels like “I actually enjoy writing code by hand” is about to become the big 2026 virtue signal for programmers. While I don't totally agree (and I think he's got a bit of audience capture staying on that site), it did cause me to question why I bother writing software for 40-year-old computers that only gets used by a handful of people and why I'm bothered by vibecoded software in this context. I write a lot of my software because I want it, but I'm also happy to make it for others in the community to use. Maybe I'm just being vain though, because I want my labor-of-love to be appreciated by people in the community I'm a part of and if a vibecoded version enters the chat with a ton of features and a slick interface, I'm afraid my work will get drowned out and it'll feel like a lot of wasted effort. My Comet will get Yahoo'd. So if a vibecoded tool is genuinely useful and available now while mine's been in development for years, maybe I should just be happy that other people in the community have something new to use. I can continue working on my version for myself and release it when it's ready. After all, Claude has to take that code from somewhere.
These are some notes for getting OpenBSD-current running on the Japanese-model Pomera DM250, DM250X, and DM250XY. Table of Contents Top Throat-clearing Making a backup Some DM250 hardware notes Making an OpenBSD installation SD card Installing OpenBSD Post-Installation Building a custom installation ramdisk Throat-clearing Much of my work has not yet been committed upstream so installation currently requires a custom kernel and U-Boot image which are provided here. OpenBSD support is still improving and may not be stable at any given time. Install at your own risk. These risks include: If the battery completely drains due to a software bug, the device may not power on correctly and will not be able to recharge its battery (see below). If the device cannot boot properly into U-Boot, you may need to recover it through a USB cable which may also require having to open the device (see recovery). Note: Do not use these instructions for the US-model DM250US yet. That device has a different power charging chip and keyboard layout. Making a backup This is optional but recommended. The tools and instructions at EKESETE.net should be used to make a full eMMC backup before doing anything. Some DM250 hardware notes The DM250's factory U-Boot detects Right Shift + Left Alt being pressed immediately after power-on and boots the recovery Linux kernel from its recovery_kernel partition instead of its normal kernel partition. The recovery kernel boots the initramfs image at the recovery_boot partition which mounts the SD card and executes any _sdboot.sh script found at its root directory. If you hold Shift + Alt too long at power-on, it will instead boot its graphical factory hardware test program. The recovery kernel and script do not show any output on the console while they boot and run. Hold down Right Shift + Left Alt + Power and count 3 seconds, then let go and it should boot the recovery kernel and _sdboot.sh from the SD card. Once the new U-Boot image is written to the eMMC (even before going through the OpenBSD installer), the DM250 will no longer be able to boot the original Linux kernel or recovery. You'll need to boot something via EFI to write the backup U-Boot image to eMMC to get back to the factory software. This can be done with the OpenBSD installation SD card created here by dropping to a shell. The DM250 will not fully power off with a USB-C cable connected to power (even with the factory Linux software). This means even if you halt -p and it powers itself off, it will immediately power back on. My U-Boot detects if the lid is closed when it first boots and if it's closed, it will halt the boot process so it doesn't boot into OpenBSD while it's closed on your desk trying to charge (though it will still be powered up to U-Boot). A working battery is required to be able to provide enough power even with a USB-C cable connected. If the battery is completely drained, it may not be able to boot up far enough to get to U-Boot for it to be able to tell the charging chip to go into a higher charge mode. By default it does a trickle charge but because it will always try to power on as soon as it has power connected, it may quickly drain the power it just added to the battery trying to boot. In short, don't let the battery drain completely. Making an OpenBSD installation SD card It is possible to install OpenBSD to the installation SD card and boot from it so the factory Linux software remains on the eMMC. It will run a bit slower (it runs slow even on the eMMC) and you will still need to write the new U-Boot image to eMMC, but you can easily revert back to the original U-Boot to resume booting Linux at a later time. These instructions assume you're running OpenBSD (any architecture). You'll need an SD card of a few GB, which is assumed to be sd1 here. Format an SD card with a GPT partition layout, making an EFI partition of at least 100MB and giving the rest to an OpenBSD partition. # fdisk -ygb 204800 sd1 # echo -e "a\n\n\n\n\nw\nx" | disklabel -E sd1 # newfs /dev/rsd1a # newfs_msdos /dev/rsd1i # mount /dev/sd1i /mnt U-Boot and OpenBSD will use that EFI partition as its firmware partition, but the original Pomera recovery software will see it as a normal MSDOS partition and run the /_sdboot.sh script contained on it. Fetch the standard OpenBSD armv7 EFI bootloader to the SD card's EFI partition as /efi/boot/BOOTARM.EFI. # mkdir -p /mnt/efi/boot # cd /mnt/efi/boot # ftp https://cdn.openbsd.org/pub/OpenBSD/snapshots/armv7/{BOOTARM.EFI,SHA256.sig} # signify -C -x SHA256.sig BOOTARM.EFI Fetch my uboot.img to the EFI partition as /uboot.img. This U-Boot image has an embedded copy of the binary device-tree built from my Linux tree for the DM250 (JP). # cd /mnt # ftp https://jcs.org/dm250/uboot.img Fetch this installation script to the EFI partition as /_sdboot.sh. This will get executed by the factory recovery partition's boot system once the DM250 is booted into recovery mode. The script mounts the EFI partition of the SD card, backs up all of the firmware files from the eMMC to the SD card, makes a backup of the current eMMC U-Boot partition to the SD card, and then writes the new U-Boot image from the SD card to the eMMC. # ftp https://jcs.org/dm250/_sdboot.sh Switch to the OpenBSD partition of the SD card and fetch the latest OpenBSD armv7 snapshot disk images to it. # cd / # umount /mnt # mount /dev/sd1a /mnt # cd /mnt # ftp https://cdn.openbsd.org/pub/OpenBSD/snapshots/armv7/{SHA256.sig,base79.tgz,comp79.tgz,game79.tgz,man79.tgz,xbase79.tgz,xfont79.tgz,xserv79.tgz,xshare79.tgz} # signify -C -x SHA256.sig *.tgz Fetch the current bwfm firmware so you can have working Wi-Fi after installation. # ftp http://firmware.openbsd.org/firmware/snapshots/{SHA256.sig,bwfm-firmware-20200316.1.3p5.tgz} # signify -C -x SHA256.sig bwfm-firmware-* Fetch my bsd.rd ramdisk image and bsd kernel. # ftp https://jcs.org/dm250/bsd{,.rd} Your SD card is now ready to go. Unmount it. # cd / # umount /mnt Installing OpenBSD Insert the prepped SD card into the DM250. If it's plugged into power, unplug it. If it's powered up, power it down. Hold down the Right Shift + Left Alt + Power buttons. As soon as the Pomera logo displays, wait about two seconds and let go. The Pomera logo will clear and the recovery kernel should now boot. It will execute the _sdboot.sh script on the SD card which will make a backup of the existing U-Boot partition to the SD card and write the new one. Nothing will be shown on the screen while it's working but it should only take about 30 seconds. Once it's done, it will reboot the device. Note that in OpenBSD, the default keyboard layout matches the Japanese keyboard on the DM250 so things like @ and * are not where they are on a US keyboard. At this point it will boot the new U-Boot with EFI support and video and keyboard drivers for the DM250. If it detected the eMMC and SD card properly, it will boot the OpenBSD EFI bootloader. No EFI variables loaded Loading Boot0000 'mmc 0' failed Booting: Label: mmc 1 Device path: /VenHw(...)/SD(1)/SD(0) disks: sd0* sd1 >> OpenBSD/armv7 BOOTARM 1.23 boot> Enter b bsd.rd to boot the installer. boot> b bsd.rd cannot open sd0a:/etc/random.seed: No such file or directory booting sd0a:bsd.rd: ... When prompted for the root disk, enter ? to see which is which. The eMMC should be sd1 showing 7.3G. Note: When installing to the eMMC, you'll need to manually setup the GPT partition table putting the EFI partition after ~16MB or so to leave room for U-Boot. This will not be needed in the future once the installer is able to recognize the DM250. Press Control + Z to get to a shell so you can manually fdisk. Use (W)hole disk or (E)dit the MBR? [whole] ^Z [1] + Suspended /install # cd /dev # sh MAKEDEV sd1 # fdisk -e -g sd1 Do you wish to write the new GPT? [n] y Writing GPT. Enter 'help' for information sd1: 1> Edit partition 0 which was auto-created, changing it to an ef partition at offset 32768 with size 8192. sd1: 1> e 0 #: type [ start: size ] ------------------------------------------------------------------------ 0: OpenBSD [ 64: 15269791 ] Partition id ('0' to disable) [01 - FF, <uuid>]: [A6] ef Partition offset [34 - 15269854]: [64] 32768 Partition size [1 - 15237087]: [15237087] 8192 Partition name: [OpenBSD Area] EFI sd1*: 1> Now create partition 1 as an OpenBSD (a6) type with the rest of the space. sd1*: 1> e 1 #: type [ start: size ] ------------------------------------------------------------------------ 1: Unused [ 0: 1 ] Partition id ('0' to disable) [01 - FF, <uuid>]: [00] (? for help) a6 Partition offset [34 - 15269854]: [40960] Partition size [1 - 15228895]: [15228895] Partition name: [] OpenBSD sd1*: 1> Print the table to make sure it matches, then w and q. sd1*: 1> p Disk: sd1 Usable LBA: 34 to 15269854 [15269888 Sectors] #: type [ start: size ] ------------------------------------------------------------------------ : Free [ 34: 32734 ] 0: EFI Sys [ 32768: 8192 ] 1: OpenBSD [ 40960: 15228895 ] sd1*: 1> w Writing GPT. sd1: 1> q # Now you can return to the installer, which is asking for disk info. Enter ? to get it to refresh disk information and it should now print out sd1. Enter e to edit the GPT (again). # fg install ? Disk: sd1 Usable LBA: 34 to 15269854 [15269888 Sectors] #: type [ start: size ] ------------------------------------------------------------------------ : Free [ 34: 32734 ] 0: EFI Sys [ 32768: 8192 ] 1: OpenBSD [ 40960: 15228895 ] Use (W)hole disk or (E)dit the GPT? [whole] e You'll now be back at fdisk, just q to quit. You can accept the auto-allocated partition layout or just make one big root and a swap partition. When prompted for the location of the sets, specify disk and then respond no that it's not mounted, and enter sd0 (the SD card), then partition a. The pathname to the sets will be just /. Continue installing, ignoring any errors from signify. The installer should automatically pick up the bwfm firmware and install it. At the end it will try to re-link the kernel which is using the upstream kernel object files, so it's important you copy the custom kernel back over /bsd. Exit to (S)hell, (H)alt or (R)eboot? [reboot] s To boot the new system, enter 'reboot' at the command prompt. # mount /dev/sd0a /mnt2 # cp /mnt2/bsd /mnt/bsd You'll also need to disable reorder_kernel which will run at each boot so it doesn't revert the kernel back to the upstream version. # mv /mnt/usr/libexec/reorder_kernel{,.disabled} # echo "#!/bin/sh" > /mnt/usr/libexec/reorder_kernel # chmod +x /mnt/usr/libexec/reorder_kernel (Note: the _ key is to the left of the up arrow, + is to the right of L.) You can now reboot. Post-Installation The first boot will report an error about bwfm and loadfirmware. You'll need to copy the firmware/nvram_ap6212a.txt file that was backed up to the SD card's EFI partition when U-Boot was flashed. # mount /dev/sd0i /mnt # cp /mnt/firmware/nvram_ap6212a.txt /etc/firmware/brcmfmac43430-sdio.rockchip,pomera-dm250.txt # umount /mnt U-Boot is compiled with boot logo support, so you can put a bitmap in the EFI partition's root directory as logo.bmp to get it to show at boot. To make it show OpenBSD puffy, you can use this image. # mount /dev/sd1i /mnt # cd /mnt # ftp https://jcs.org/dm250/logo.bmp # cd / # umount /mnt The two LEDs near the USB-C port can be addressed once booted. Create an /etc/rc.securelevel that sets them up so they are accessible from a normal kern.securelevel: # cat > /etc/rc.securelevel #!/bin/sh gpioctl -q gpio1 8 set out red_led gpioctl -q gpio1 12 set out green_led ^D # After rebooting, they can be addressed with the gpioctl utility: # gpioctl gpio1 8 1 pin 8: state 0 -> 1 Building a custom installation ramdisk If you want to tinker beyond installing, you'll need a Git clone of my OpenBSD rk3128 tree, my U-Boot pomera-dm250 tree with video and keyboard drivers, and my Linux tree which contains the DTB source files. This is optional and requires being able to compile on an armv7 machine (or cross-compile if you know how), or you can just download the latest image I've already built. Fetch an existing bsd.rd, extract its installation filesystem, build the RAMDISK kernel from my rk3128 tree, and then insert the filesystem into the new kernel. $ cd /tmp $ ftp https://cdn.openbsd.org/pub/OpenBSD/snapshots/armv7/bsd.rd $ rdsetroot -x bsd.rd root.fs $ cd /usr/src/sys/arch/armv7/compile/RAMDISK $ make config $ make $ cp -f obj/bsd /tmp/bsd.rd $ rdsetroot /tmp/bsd.rd /tmp/root.fs The /tmp/bsd.rd file is now a bootable installation image with a custom kernel.
A new release of my Wallops IRC client is available: wallops-2.2.sit (StuffIt 3 archive) adc2b473664ec0960b5b028335566831dd69f4a1de40f79e22bf1337292cca88 SHA1: 603c5080c41a0d5752cae49a08376db4e18628b1 This update includes a number of new features and bugfixes: Auto-connect with the last saved settings on startup, if they are available, unless the Command key is held down Add support for sending Pushover notifications when the user's nick is mentioned or directly messaged, when a screen saver is detected to be running; sends to Pushover's API over plain-text HTTP Improve nick highlighting when the user's nick is not at the beginning of the line Speed up parsing of nicknames when joining large channels Add support for the /monitor command which is sent directly to the server Fix bug that may have caused a crash when initially connecting, and when reconnecting
More in technology
Sharing a few data points because some people did not expect these drives to last that long.
I'm 100% for banning social media for children. I would even extend it to banning it all together in its current form. But I am also against the methods for enforcement. The problem with banning social media for one group and not another is that you have to differentiate the different groups somehow. And right now, in an age where information and personal data means everything, there are several entities that are salivating to get this data. I've written before about all the problems that come from uploading sensitive data online. It doesn't even matter if they delete the data afterward, as long as the data goes through the wire in the first place, there is a chance for a leak. What appears to be the same simple request "please verify your identity", becomes fundamentally different when mediated by technology. The question isn't whether these digital systems will be compromised, but when. And unlike that movie theater clerk who can't perfectly recall my birthdate minutes after seeing it, computers have perfect memory. They store, copy, backup, and transmit our most sensitive information through networks we don't control, to companies we've never heard of, under policies we'll never read. When kids are not allowed to use social media, it's the adult who pays the price. It's the adult who has to prove that they are not children. They have to risk uploading their government ID to a third party, or biometric data that may be saved and backed up forever. I reject this method. I also reject the method where I have to provide my age to the operating system. No system should compel me to provide personal data in order to use it. Especially if this feature is intended to provide the information to a third party. And what happens if I don't provide this information to my freebsd machine? Or worse, what if I provide false information? Am I going to get punished? How does that protect children in any way? Breaking news: Grown up arrested when OS reported forged identity in his laptop. One question I asked myself was what happens when a minor circumvents the ban. What are the consequences? At least in Australia, a country that has implemented a social media ban for those under 16, there are no consequences. The law places legal responsibility on platforms, not children or parents, and it currently applies to Facebook, Instagram, Kick, Reddit, Snapchat, Threads, TikTok, Twitch, X and YouTube. This almost sounds reasonable. Why should you care, if it becomes facebook responsibility when you don't even own a facebook account? But there is always a caveat. When facebook becomes a tool your school uses to communicate with parents. When Google classroom is the service students use to do their homework. When you are required to login on a system to receive government service. You may not care about a particular social media, but they raise the bar for every other entrant in the game. Every website frequented by a large number of people inherently become social media, and demand data you didn't need to provide before. Technology is not a magical thing that can just solve every problem. It is especially weak when it comes to social problems. However, society can use technology to solve their problems. The responsibility of children falls onto their parents. And there are great tools for parents that their kids access on their devices.
Introduction Hamming Distance Intuitive Estimation of Error Correction Bits Digging Deeper Comparing against BCH Codes What about Reed-Solomon Codes? BCH vs Reed-Solomon Codes References Footnotes Introduction I’ve been interested in error correcting codes (ECC) for a while now, and though I haven’t gotten very far, I keep on reading and, occasionally, writing about it. Except for really simple schemes, ECC theory gets complicated quickly. The two codes that I’ve looked at most are Reed-Solomon (RS) and binary Bose–Chaudhuri–Hocquenghem (BCH) codes. They are closely related: both use polynomial math that is normally performed over a Galois Field, though, as shown in my earlier Reed-Solomon blog post, that’s not strictly required. The encoding algorithms are relatively straightforward but the decoding algorithms are significantly more complicated. RS and binary BCH codes differ in the size of their symbols, their alphabet: a symbol of the former consists of multiple bits, often 8 bits, while a symbol of the latter is a bit. Errors are corrected with a granularity of a symbol. One key ECC question is “How many additional bits do I need to correct a given number of errors?” In this blog post, I check if an intuitive approach that I’ve been using matches reality. I’m trying hard to stay away from theory here, which makes the subject hopefully more accessible, but has the flip side that it’s far from being rigorous and exact. Hamming Distance When you look at the theory of error detecting and correcting codes, the discussion immediately turns to Hamming distance: the number of bit flips required to convert one vector of bits to another. The goal of an error correcting code is to transform the input vector, the message, to an output vector, the codeword, so that the minimum Hamming distance between valid codewords is guaranteed to be at least a certain number. The higher the Hamming distance, the higher number of bits that can be flipped in a codeword without destroying the ability to recover the original message. If \(t\)1 is the number of errors that we want to correct, error coding theory gives us the following formula: In words: to correct a codeword with a maximum number of \(t\) bit errors, the Hamming distance between any 2 codewords must be larger than two times \(t\). The theory also tells us the minimum Hamming distance to detect an error without correcting it: In the rest of this blog post, though, we’ll only care about correction, not detection. Here are 2 quick examples where the message is one bit. Adding 1 bit to the message For a one bit message, there are only 2 possible messages, 0 and 1. Let’s use a code that repeats this bit once: 0 becomes 00 and 1 becomes 11. The Hamming distance between these 2 valid codewords is 2 because you need to flip 2 bits to convert 00 into 11. The equation above tells us that a distance of 2 is not sufficient to fix a one-bit error. Indeed, when we receive 01 as a codeword, it’s impossible to tell if the transmitted codeword was 00 or 11: both have a Hamming distance of 1 to the received word of 01. Adding 2 bits to the message When we expand the 1 bit message to 3 bits and repeat the message bit twice, things are different: 0 transforms into 000 and 1 into 111. The Hamming distance between all possible codewords is 3. The theory says that we should be able to correct a codeword for which only 1 bit was flipped. And indeed, if we receive 001 and there is only 1 bit corrupted, we know for sure that the original message was 0. Intuitive Estimation of Error Correction Bits The concept of a minimum required Hamming distance to correct a number of errors is not particularly complicated, but it’s a different matter to use it to determine the number of additional ECC bits for, say, a BCH code. In fact, I still don’t know how to do it. As an alternative, I found myself using a simple model that works like this: Participant A transmits 1000 bits to participant B over a noisy channel B transmits the same 1000 bits back to A over a perfect channel A transmits a 10 bit error index to signal to B which bit it received wrong Or more general: If a message of \(k\) bits has 1 incorrect bit, you need a number of \(r = \lceil \log_2(k) \rceil\) 2 bits to point out the incorrect bit. Let’s call that number the error index3. To correct \(t\) bits, you need up to \(r = t \cdot \lceil \log_2(k) \rceil\) additional bits. That’s it! The model is simple, it’s not exactly practical, and the number of parity bits has to be only a first order estimation, but I felt like it had to be pretty close to reality. But is it? Digging Deeper Let’s consider some of the aspects of this model: There is no way to signal that there was no corruption That can be solved by allocating one error index value extra to signal a perfect transmission and calculate the number of bits as \(r = \lceil \log_2(k+1) \rceil\) instead of \(r = \lceil \log_2(k) \rceil\). E.g. for a 1000-bit message, an error index from 0 to 999 indicates an error location, and 1000 signals perfect transmission. For messages that are not a power of 2, the number of error indicator bits remains the same. The transmitted error indicator bits can be corrupt as well One way to solve this is by going through the same procedure to verify the error index. For a first iteration, it would cost an additional \(\lceil \log_2(\lceil \log_2(k+1) \rceil ) \rceil\) bits, 4 bits for a 10 bit error index. Of course, those 4 bits might be corrupt too! A better approach is to work backwards: start out with the length of the codeword and the number of errors you want to correct and determine the number of input message bits from there. The number of error indicator bits is then calculated over the length of the codeword and you get \(r = \lceil \log_2(n+1) \rceil\). The length of the message is \(k = n - r\). This breaks the simple model where you transmit message and error indicator separately, but that was not a realistic scenario anyway. It doesn’t consider that the same error index can appear only once If the code can correct 2 errors, you’d need \(\lceil \log_2(k+1) \rceil\) bits for the first error index to indicate zero errors or the location of the first error. For the second error, you need one less value because one location has already been corrected, so the number of bits needed is \(\lceil \log_2(k) \rceil\). This suggests that the number of error indicator bits might be an upper bound. It only applies to error correction the way BCH does it Any random bit can be corrected, but it doesn’t work for RS coding because there a whole symbol can be incorrect. That’s fixable though, I get to that later. You don’t need to signal the correct value Since the symbol is 1 bit in size, the location of the error is sufficient. To fix it, the receiver just needs to invert the bit. This also doesn’t work for RS. Comparing against BCH Codes Forget about using the Wikipedia article to compare the intuition against theory: you won’t find anything explicit. I found this presentation from the National Taipei University useful. The key formulas are on the first slide: Block length: \(n = 2^m -1\) Number of parity-check bits: \(n - k \le m t\) Minimum distance: \(d_{min} \ge 2t + 1\)4 In the equations above, \(k\) is still the length of the original message, \(t\) is the number of bits that can be corrected, \(n\) is the length of the codeword. If we rearrange the first equation, we get: Substitute \(m\) in the second equation: \(r\) is the number of error correction bits, so \(r = n - k\) and: Compare this with the intuitive formula that I started with: The only differences are: I used \(k\) instead of \(n+1\). That accounts for the fact that parity bits themselves need error correction too and that a perfect transmission must be signaled. the BCH equation assumes that the total codeword length is always one less than a power of two. instead of an approximation, it defines an upper bound. Theoretically, all BCH and RS codewords have a length \(n = 2^m -1\) symbols. In practice, the transmitted codewords are often shortened by setting a bunch of the symbols in the input message to zero and not transmitting them.5 When using shortened codes, you still have to use the \(m\) value of the parent code for which \(n = 2^m -1\). The intuitive formula works for long codewords and a limited number of errors to correct: \(n \approx k\). What about Reed-Solomon Codes? RS codes correct symbols not bits but you can still use the intuitive formula to identify the corrupted symbol: in a message with, say, 223 bytes you’d need 8 bits to pinpoint an incorrect byte. However, you also need an additional byte to fix the corruption and that is the case for every error byte that needs to be corrected. To repair \(t\) symbols that are \(s\) bits in size in a message of \(k\) symbols, you’d need this number of bits for the error location: And a bunch of bits with the correct values: Note that \(r_{location}\) points to a symbol, not a bit. Just like BCH codes, \(n = 2^s - 1\) for RS codes. Change \(r_{location}\) to use \(n\) instead of \(k\) and you get: The final result is: It turns out, that is exactly what you’ll find in all texts about RS coding: the number of parity symbols must be at least 2 times the number of corrupt symbols you want to correct. BCH vs Reed-Solomon Codes I’m getting a bit off-topic here but with the intuitive formula validated, it’s interesting to see when RS codes are better than BCH and vice versa. Let’s create an example where codewords are 255 bytes or 2040 bits and where we reserve 32 bytes or 256 bits for error correction. For RS, this allows us to correct 16 corrupt bytes that can contain up to 128 corrupt bits, as long as they’re contained within those 16 bytes. For BCH, we need 11 bits per error or \(11 \cdot 23 = 253\) parity bits to correct 23 corrupt bits which fits within the 256 bits that were allocated for RS. RS is the winner if errors happen in bursts: it doesn’t matter if a burst is 1 or 8 bits long, it counts as a single corruption when they fall within the same byte. BCH wins when errors are spread randomly: instead of fixing 16 bit flips, it can fix 23. In practice, communication protocols often used 2 codes in the following scheme: Transmitter: RS Encoder -> Interleaving -> Convolutional Encoder Receiver: Viterbi Decoder -> De-interleaving -> RS Decoder In this setup, RS is called an outer code and convolutional coding the inner code, because they wrap around the transmission in that order. In many transmission mediums, bit error are uncorrelated and burst errors unlikely. One would think that RS coding is the wrong choice then. However, the Viterbi decoder can introduce bursts of errors when it makes a mistake. The RS decoder is used to clean those up. The burst error length can be so long that a single RS codeword can’t deal with them. That’s why there’s an interleaver to increase the length of burst errors that can be corrected, at the expense of latency and memory storage, but that’s a topic for a different blog post. Modern communication protocols, such as DVB-S2 that’s used by satellite TV, use a low density parity check (LDPC) code instead of a convoluational code as inner code. A LDPC decoder has a lower tendency to introduce long error bursts in case of a mistake and instead introduces single bit errors that are spread randomly within a large codeword. This is where BCH codes shine which is why it’s used instead of RS. All words in this blog posts were written by a human. References Reed-Solomon Error Correcting Codes from the Bottom Up National Taipei University - BCH code CMU Introduction to Coding Theory - Notes 4: Elementary bounds on codes NASA - Bandwidth efficient CCSDS coding standard proposals Discusses outer coding/interleaving/inner coding for space communication. There’s an abundance of information in there, which is what you’d expect from a 70 page document! Footnotes In literature, you’ll often see \(k\) being used for this formula, but further down, \(k\) is used as the length of the original message, which is also a literature convention. So I decided to be consistent within this blog post. ↩ \(\lceil x \rceil\) means: round up to nearest integer. ↩ I came up with “error index” myself, but it turns out to be a term that is commonly used in error coding theory and its meaning is exactly what I had in mind! ↩ This is the minimum Hamming distance equation for error correction. ↩ This assumes that a systematic coding scheme is used, where the original message appears unmodified in the codeword. This is the case for most BCH and RS coding schemes that are used in the real world. ↩
Plus Thomas Ableman on what we can learn about AI from the Victorian railway rollout
Water-resistant microneedles made from food-grade silk could deliver vaccines to help prevent the spread of disease in aquaculture.