brainwagon

Last night while watching television, I decided to code up an SSTV modulator for the most popular US mode, which is reportedly Scottie 1. I had done most of the heavy lifting when I created a Robot36 encoder a few years ago, so I mostly cribbed the meat out of that code, and modified it to do the details of Scottie 1, which (since it is in RGB space rather than YUV) is rather simpler than the original code. Once I had that working, I decided to do some experiments using Multiscan, an SSTV decoder that I had on my Macbook Pro.

First, I needed some source material. I chose this picture of myself in front of the Tower of London, for no other reason than simple expediency. It does however have some nice features. It contains a faily uniform sky background, and then the tower itself is highly detailed, but with fairly low contrast. Here is the original, which was downsampled to 320×240, padded with 16 lines of gray, and then upsampled to an easier to view 640×512. Consider this the “ground truth” image. (Click on the image to view it full resolution)

Using my modulator code, I then encoded it in Scottie 1 mode. I then used a loop back cable to play it back into the line input on my Macbook, and fed it to Multiscan, the better of the two programs that I know to do SSTV on the Mac. Here’s the resulting image:

Not exactly stellar. In fact, downright blurry. I wasn’t too pleased with the quality of this. My suspicion is that MMSSTV will do a better job, but I left my Windows laptop at work, so I can’t really be sure. It’s also possible (although I think somewhat unlikely) that my modulator is the source of the blurriness.

I also made a version of the audio file with some fairly strong additive white Gaussian noise added.

Multiscan wasn’t able to get the sync properly at this signal to noise ratio. I find that a little surprising, it seems to me rather straightforward to solve this problem. You can also see that the overall quality is quite a bit lower.

So, I’m curious: do any other SSTV decoders do better? In the interest of trying to find the best performing decoders, I will put links to the uncompressed 11025Hz .WAV files which I used for these tests. If you try them out with your favorite SSTV decoder, feel free to drop me an email with the decoded images (or links to them on flickr or picasa or whatever) along with details of what software you used, and whatever special operations or processing you did. If I get any good response, I will summarize in a future posting.

Scottie 1 SSTV, WAV format, 11025Hz sample rate, no noise.
Scottie 1 SSTV, WAV format, 11025Hz sample rate, substantial additive Gaussian white noise.

Thanks for any response! In the future, I’d like to do a more systematic evaluation of analog SSTV modulators, demodulators, and modes.

Addendum: For my reference on the implementation of modes, I used JL Barber’s excellent paper on SSTV modes. In his description of Scottie 1, he says that the first scanline has an anomalous sync pulse (9ms of 1200 Hertz). When I tried that with Multiscan, it never got started: it seemed to have some problem. When I deleted that sync pulse, everything starts as expected. If anyone tries this experiment, I’d like to hear of any failures to start. Also, if anyone knows of any definitive Scottie 1 examples on the web, let me know.

My recent playing with SSTV images coming from ARRISSat-1 have made me think a bit more about SSTV. I used two different applications to decode SSTV images (MMSSTV on Windows, and Multiscan on OS X), and got slightly different results in terms of performance from each. This leads me to ask “just what are the limits of performance for analog SSTV imagery, and how closely do existing applications approach these limits?”

Whenever I ask a question like this, there seems to be two complementary approaches: doing research and doing experiments.

Luckily, courtesy of Google, research has never really been easier. Relatively quickly I found this article by Lionel and Roland Cordesses:

Some Thoughts on “Real Time” SSTV Processing by Lionel and Roland Cordesses, QEX May/Jun 2003

It’s a great article, with many good ideas. The authors have apparently implemented them in the F2DC SSTV program, which apparently in need of some repair (written for Borland tools and Win95) but could provide the basis for a new, good implementation. But their paper provides some basic ideas, and I’m not sure I agree 100% with their implementation of them, so perhaps it is more valuable as inspiration.

They use a fairly old but still useful technique based upon the Hough Transform to do high quality deskewing of the incoming image signal. Much of the paper is devoted to details of making that work. In the past, I’ve used RANSAC to figure out sync pulse locations in my NOAA satellite decoder. Their technique is almost certainly less computationally intensive, but RANSAC can match more complex models (including Doppler shift, which is important for NOAA images), and I find RANSAC less “fussy” to implement (it is relatively indifferent to the model you choose, which makes modularization easier).

The other part of their paper deals with robustly estimating frequency. The simplest (and worse performing) demodulators estimate frequency from just two or three samples surrounding the current pixel location. The authors instead determine frequency by convolving a window function 37 samples long around the current position (they are sampling at 44100 samples per second) or about .83 ms. In the Martin-1 mode they use, a pixels is about .57ms long, so they are looking at a window of just about 1.5 pixels. That seems okay to me, but I’m confused by some of the choices.

They choose to digitize at 44100, which seems excessive to me. SSTV information is confined to the regions between 1200 and 2300 Hz, so according to the Nyquist theorem, even sample rates of 8Khz contain all the information needed to do a decode (assuming the signals actually are bandwidth limited). I was thinking of using 11025 samples per second. The corresponding window functions that would correspond to the 37 tap filter would be about 9 samples long, which would still provide the same level of frequency discrimination, but at a lower computational cost. I can’t imagine any practical reason to use finer sampling (DSP experts can point out any errors in my thinking in comments).

The cool part of their system is that they estimate the signal to noise ratio of the signal (by comparing power inside and outside the SSTV bandwidth) and use longer filters to estimate frequency when the SNR is poor. This makes a tradeoff between resolution and noise immunity, which seems in practice to be quite effective.

It would be interesting to make modern implementation, using gcc and fftw3 as a basis, and documenting all of the design choices. I think it would also be good to test the decoders against both AWGN (additive white Gaussian noise) and perhaps using an HF channel simulator to judge their performance. I’m most interested in the Robot36 mode, since that seems to be a common choice for satellites, but Scottie and Martin modes are also essential.

If anyone else has any interesting references on SSTV transmission and reception, feel free to add them via comments.

Courtesy of a new $1.99 app called Word Foto, I give you:

Some of you may remember that I wrote my own APT satellite decoder. I ran across someone else who did the same:

ATPDEC by Thierry Leconte (F4DWV)

It has the same basic philosophy as my own crude efforts: hand it a WAV file, and it will find and produce the APT imagery from inside it. I went outside and recorded some of the NOAA 19 pass over my location today, and came up with the following:

Pretty nifty! I did have some trouble with some of the older recordings though: I suspect that noise may toss off his calibration in some way which isn’t entirely obvious. I’ll have to play with it more.

I got pointed at this rather large collection of shortwave recordings which are archived on the archive.org website:

Shortwave Pirate Radio : Free & Unlicensed Shortwave Radio Stations : Free Download & Streaming : Internet Archive

They have many crazy recordings of radio pirates, some of which are pretty dull, but some of which were pretty interesting. I was interested to find that there was a recording of a “digital” pirate radio station: station “XYZ”. It was easily recognizable to me as being transmitted in Hellscrieber, an old fax-like mode that was developed in the 1920s. The amateur software “fldigi” is capable of decoding these signals, which looks like this:

There is lots of fading in the recording, but it’s still quite legible. I’ve often thought making a small QRP Hellscrieber rig would be an awesome project. Oh well, I just thought it was mildly interesting.

I was interested in WSPR and visual MEPT oeprations for quite some time. I operated both a beacon and a QRSS aggregator on 30m for a while, but I grew a bit tired of it, and it’s been silent for a year or so. But I haven’t stopped thinking about them. In fact, I’ve had an idea percolating in the back of my head since last year, when I became aware of the work of Leemon Baird and William Bahn on Jam Resistant codes.

But I’m getting ahead of myself. Here are some of what I think could be improved with WSPR:

1. WSPR requires accurate clocks both for receiving and transmitting. To be successfully decoded, transmissions must start within a window just a few seconds long surrounding even numbered minutes. This makes both sending and receiving systems complicated: they probably need to access an external reference (NTP, GPS or WWV) to operate reliably over an extended period.
2. Fixed frequency operation can cause collisions. Each transmitter selects a fixed transmit frequency, and relies on multiplexing over time to avoid collisions. WSPR software itself provides no real help in selection of an appropriate free frequency.
3. The choice of a convolutional code is somewhat odd. The payload is only 50 bits long, but we pad the results with 31 zeros to flush out the convolutional coder. Thus, we are actually getting the error correction of a rate 1/2 code, but we are only sending as much data as if we were sending a rate 1/3 code.

I had been pondering some of these issues, when I became aware of the work of Baird and Bahn. They are researchers for the Air Force Academy, and were particularly studying the problem of providing jam proof communications without the need for shared secrets. Briefly, you can imagine using spread spectrum to provide a measure of jam proofing: because the data is spread out among many frequencies over time, the spread spectrum signal has a good measure of jam proofing: the jammer needs to put energy over most of the frequency most of the time, where as the transmitter can put his full power on just one frequency at a time (other variants of spread spectrum are a bit different, but the principle holds). The only way a jammer can work efficiently is by knowing the sequence, which is usually a cryptographic secret.

This is where Baird, Bahn, and Collins’ work comes in: In their paper:

Baird, Leemon C. III, Bahn, William L. & Collins, Michael D. (2007) Jam-Resistant Communication Without Shared Secrets Through the Use of Concurrent Codes, Technical Report, U. S. Air Force Academy, USAFA-TR-2007-01, Feb 14.

they show a simple technique that can be used to transmit signals with high reliability and a high degree of jam resistance, without requiring any kind of shared secret or cryptography.

The idea is somewhat subtle, but reasonably straightforward. The idea is to create take the binary message (say, the same 50 bits that we use for WSPR). This message gets padded by a series of zeros (maybe lots of them, perhaps a multiple of the original message length). You then need a hash function (some details matter, but you can think of using a standard one like MD5 or one of the SHA variants if you like). Now, for each prefix of the message (bit streams of length one, then two, then three, and so on), you compute the hash of that prefix. Let’s say that you are going to transmit the message by sending short, powerful bursts of energy at particular times in particular window. (You can imagine this being the two minute window used to transmit WSPR to make it more practical). If we divide that into (say) 8192 slots, then we could take each hash, take the lower 13 bits, and use that to specify a particular time when that bit would get turned on. If we send 500 bits total (9 zero checksum bits) for every real one, we are sending about 500/8192 slots, or about 6% of the total. To mark the start and stop, let’s turn on the first and last bit. That’s pretty much the entire transmit side.

What’s cool is that you can decode the message on the remote side, and if you ignore efficiency, it isn’t even that hard. Let’s say that you located a stretch of bits 8190 long, between two on bits. That might be a message. So, how do you decode it? Well, the first bit might be a zero or a one. You basically pretend that you are transmitting, and encode both messages. That will return a location, which you check to see is on. If it isn’t, then you know that guess was wrong. If it is, then that hypothesis is good. It’s possible that none could be right. That means there is probably not a message in that span. It’s possible that one could be right, in which case you then add a zero, and then try adding an one, and seeing if the hypothesis still holds. There are times when both results will check out, but statistically it is unlikely. When you hit the “checksum bits”, you know that there is only one possibility: a zero. If the specified hash doesn’t yield a location that is turned on, you know that you are on the wrong track. (The overall algorithm reminds me somewhat of a Viterbi style decoder, although it is actually considerably simpler).

There are lots of details to make this efficient (you want a hash function which allows incremental updates as you add individual bits to the message) but it’s pretty straightforward.

Anyway, I think this could be the basis for a new highly-collision resistant beaconing protocol for amateur radio. It would enable very simple transmitters (a simple microcontroller could hold the sequence in internal EEPROM, no need for highly accurate clocks) and the system would be more highly jam resistant than the current system. We could use simple CW transmissions, or adapt to slower rates with more diverse frequency usage. And, the technology has been paid for by your tax dollars, so no pesky patent/IP issues would seem to apply.

What do people think? I’m interested in hearing some feedback from digitally minded radio amateurs.

Addendum: if my descriptionw as insufficient, try reading the papers (especially Visually Understanding Jam Resistant Communication) and/or posting some questions in the comments.

I found this manual to be informative as I continue my quest to making a properly functioning 8080 emulator. I’m learning lots, but still not quite there. This is just bookmarked for future reference.

Digital Research CP/M ® Operating System Manual.

I overslept this morning, and woke up a scant 10 minutes before this morning’s good pass of ARISSat-1 was to begin. Still, all I had to do was go out to my car, grab my Arrow, and my HP laptop, and my trusty VX-3R, and I should be able to make it. I started pulling on my shorts and shoes, and then remembered that my HP laptop had not been plugged in, and the amazing penchant for laptops to discharge when not fully shut down would mean that it was likely it’s battery was dead. No problem, think I. “I’ve still got my Macbook, and it was plugged in.”

I quickly fired up the Macbook and reacquainted myself with the pass. Yep, should start in about 4 minutes, peaking at 72 degrees or so. Nice! I grab my car keys and head outside to fetch a camp chair, my Arrow antenna and the radio.

But when I pop the back, I find that unlike what I expect, my VX-3R isn’t there. I can’t remember: did I bring it in to be recharged? Oh well, I have my VX-8GR which I use in my car as well, and that’s fully charged up. I quickly shift it over to 145.950, and attach it to the Arrow. Even though the antenna is aiming straight down I can still easily hear the voice from the beacon coming in. I scramble for a little patch cable so I can get it hooked to the laptop.

Then I remember: unlike the VX-3R, the VX-8GR has a combination speaker/microphone output, and the normal patch cable that I use with great success on the VX-3R doesn’t work on the VX-8GR. I need some crazy adapter, which I may or may not have. Sigh. On well. I shift Audacity over to record from the laptop microphone (meaning I’ll get road noise from passing cars, and wind noise) but that’s the only way that I will salvage the pass.

I got two SSTV images, as well as some nice recordings in French and Japanese. Sadly, but somewhat predictably, the best image was the standard logo, and the more interesting image was happening as the satellite was approaching the horizon. Still, best I’ve gotten in a while.

The horizontal bar in this one was caused by a gust of wind. Still, not bad.

Toward the end of this one, I was losing the signal pretty badly. I’ve used lots of noise reduction, which helped a tiny bit.

I’ll try to be better for tonight’s high pass.

Addendum: I found the little pigtail doohickey (a Yaesu CT-44, in case you need one) in an astoundingly short period of time. The way that ham radio equipment manufacturers pad their margins by requiring custom cabling (this little gadget costs around $15 from HRO) is shameless. Not only do I have to pay for it, but I have to remember to keep it in my equipment bag for the times I need it. Argh. Oh well, I’ll have it ready for tonight’s pass.

Okay, not 8080 bottles, but 99 bottles of beer anyway…

[proof:~/adad] markv% ./adad
::: brainwagon 8080 emulator version 1.0
::: 637 bytes of code loaded.
99 bottles of beer on the wall, 99 bottles of beer.
Take one down, pass it around, 98 bottles of beer on the wall.
98 bottles of beer on the wall, 98 bottles of beer.
Take one down, pass it around, 97 bottles of beer on the wall.
97 bottles of beer on the wall, 97 bottles of beer.
Take one down, pass it around, 96 bottles of beer on the wall.
96 bottles of beer on the wall, 96 bottles of beer.
Take one down, pass it around, 95 bottles of beer on the wall.
... output trimmed for the sake of brevity ...
5 bottles of beer on the wall, 5 bottles of beer.
Take one down, pass it around, 4 bottles of beer on the wall.
4 bottles of beer on the wall, 4 bottles of beer.
Take one down, pass it around, 3 bottles of beer on the wall.
3 bottles of beer on the wall, 3 bottles of beer.
Take one down, pass it around, 2 bottles of beer on the wall.
2 bottles of beer on the wall, 2 bottles of beer.
Take one down, pass it around, 1 bottle of beer on the wall.
1 bottle of beer on the wall, 1 bottle of beer.
Take one down, pass it around, no more bottles of beer on the wall.


::: 53132 cycles counted.
::: 0.00 seconds elapsed.
::: 0.03 seconds on a 2Mhz 8080.
::: 11.50 x speedup.

After getting a version of Tiny BASIC running on my emulator, I was scanning around to try to find something else to run. And, of course, when you look, you find all sorts of cool stuff. I happened across this cool page which is an 8080 emulator which is written in Javascript, and runs entirely in the browser. Very neat.

Intel 8080 CPU Emulator.

I’ve made a tiny bit of headway, but also encountered a link which makes me envious of much greater hacking skill. Óscar Toledo did an 8080 emulator that can boot CP/M as part of the 19th International Obfuscated C Code Contest, winning Best of Show. Its brevity is the “soul of wit”. Check it out.

Toledo 8080 emulator

Óscar also has written several tiny chess programs, and a Javascript chess program. Awesome.

While I didn’t find his code to be all that helpful (it’s, well, dense to say the least), I did find his approach to be helpful. A few additional minutes of hacking, and I managed to get the Tiny BASIC that he runs on his simulator to work on my own. Witness the following BASIC program:

>LIST
  10 PRINT "A PROGRAM TO EXPLORE THE 3 * X + 1 PROBLEM"
  20 FOR I = 1 TO 10
  25 T = I 
  30 GOSUB 100
  35 PRINT
  40 NEXT I
  50 STOP
 100 PRINT T,
 110 IF T = 1 GOTO 1000
 120 LET J = T / 2 
 130 IF 2 * J # T GOTO 140
 135 LET T = J
 136 GOTO 100
 140 T = 3 * T + 1 
 150 GOTO 100
1000 PRINT
1010 RETURN

OK
>RUN
A PROGRAM TO EXPLORE THE 3 * X + 1 PROBLEM
     1

     2     1

     3    10     5    16     8     4     2     1

     4     2     1

     5    16     8     4     2     1

     6     3    10     5    16     8     4     2     1

     7    22    11    34    17    52    26    13    40    20    10     5    16     8     4     2     1

     8     4     2     1

     9    28    14     7    22    11    34    17    52    26    13    40    20    10     5    16     8     4     2     1

    10     5    16     8     4     2     1


OK
>

Not bad! I suspect that even though my 8080 simulator is still pretty rough, I could get CP/M booted on it in much the same way that he did. More later.

I spent some more time hacking on my emulator today. The key to getting an emulator to work is to have good, clear references on how the system works, and some example code that torture tests your simulator. Except for the DAA instruction (more on that later), the documentation for the 8080 is pretty good, and reading about several of the VHDL and Verilog simulations of the 8080 turned me onto CPUDIAG.ASM, a program which was designed to exercise the 8080 (apparently early NEC clones of the 8080A had difficulties with the DAA instruction). As it turns out, this little chunk of code proved to be incredibly useful.

;***********************************************************************
; MICROCOSM ASSOCIATES  8080/8085 CPU DIAGNOSTIC VERSION 1.0  (C) 1980
;***********************************************************************
;
;DONATED TO THE "SIG/M" CP/M USER'S GROUP BY:
;KELLY SMITH, MICROCOSM ASSOCIATES
Click here for the complete source.

After a couple of hours more tinkering, my efforts were rewarded with:

::: brainwagon 8080 emulator version 0.0
::: 1453 bytes of code loaded.

 CPU IS OPERATIONAL

Huzzah! Okay, there are still a few things this thing doesn’t test, like interrupts and the like. And I couldn’t figure out how the DAA instruction is supposed to work. It’s not clear to me that SIMH implements this properly either, a quick peek at their code seems to show that none of the ADD instructions do anything to set the auxillary carry bit. For now, I just commented out the offending tests. I’ll put them back in when I have some confidence that I understand how they are supposed to work.

Now that the instructions basically work, it appears that the next thing to do would be to try to figure out how to boot CP/M on the virtual machine. Then… tidy it up to see if I can shrink the code (the code for my linux box is about 12K). Then… well, we’ll see.

I’ve been trying to get out and record more ARISSAT-1 passes, in the hopes of getting some nice SSTV images. If you follow @brainwagon on twitter, you are likely to see some of the more mundane images that I’ve been getting thusfar. I keep hoping to snag some truly great ones, but thus far, the earth seems to be really good at evading the lens of ARISSAT-1 while it’s above my radio horizon. For instance, today I got these two pictures:

Not exactly exciting. There is an 82 degree pass later today, maybe I’ll luck out.

One thing that might not be obvious is that ARISSat-1 has four cameras. You can tell which camera is in use by looking at the color of the RS01S logo in the upper left of the SSTV image.

• Red indicates the camera pointing along the -Y axis.
• Green indicates the +Z camera. You can sometimes see the 2m antenna in this view (as you can in the green logo image above, poking in from screen right).
• Blue is -Z pointing view, out the “bottom” of the satellite.
• Magenta is the +Y pointing camera.

When I look at the ARISSat-1 SSTV gallery hosted by AMSAT, I see that most of the “good” pictures come from the blue and magenta cameras, but it seems clear that the orientation of the satellite drifts a bit, and there is no guarantee. I’ll just keep plugging away until I get something better.

One of the more gratifying benefits of blogging is that it provides an opportunity to meet people who share your interests and enthusiasms. A few months ago, I became aware of the crew on the #savagecircuits IRC channel on AfterNET and started hanging out there. Various group members like Atdiy, whisker, JohnS_AZ, MakerDino, and Roy_Eltham (and others) all have participated in Ustream sessions, group Skype calls, and even played some Minecraft together. It’s a fun group.

Atdiy and whisker have started a new podcast called “Zombie Tech” which is basically just an extension of these online sessions. Nominally, the purpose is to pool our geek talents to figure out how we might survive the inevitable Zombie Apocalypse™, but as serious as that is, we seem to spend most of our time talking about some of the geeky projects we are engaged in, trying to teach each other and learn more about electronics, microcontrollers, programming, and using the Internet to spread more enthusiasm for more of the same.

They asked me to be on this week, and we talked for an hour. I’d be interested in hearing any feedback (hopefully positive and constructive, but any is welcome). And thanks to Atdiy and whisker for inviting me on.

ZombieTech – Zombie Tech 004.

A couple of days ago I got intrigued by this cool project which ran CP/M on an AVR. The basic idea was to equip an AVR with an external RAM, and then write a compact 8080 emulator to run on the AVR. Instead of floppy drives, the AVR accesses data stored on a small SD card. I thought it was really cool.

So I decided to see how far I could get.

A couple of hours work spent watching TV had the basic framework in place, and it’s beginning to execute code. For instance, here is the simple “Hello World” program, written in 8080 assembler (it presumes that you are running on a CP/M system to supply a printing system call):

bdos    equ     0005H
        org 0x100
start:  mvi c,9
        lxi d,msg
        call bdos
        hlt
msg:    db 'Hello World!', 0xA, '$'
end     start

Unless you like assembling code by hand, you need an assembler. I thought about using a simulated CP/M system running on simh, but that quickly got annoying, so instead I searched around and ultimately stumbled on asmx, a multi-CPU assembler which seemed to work just fine. It produced a nice little Intel hex format file, which my emulator can then load. I trap calls to the BDOS entry vector, and implement them with standard C calls (at the moment), and the net result is the rather unimpressive:

::: brainwagon 8080 emulator version 0.0
::: 23 bytes of code loaded.
Hello World!

Most of the control functions work, I need to get the conditional returns to work properly. I don’t have interrupt support yet, nor does it compute cycle counts, but the overall framework is quite good. I suspect that another couple of hours of work will get 95% of the instructions working, and then I could consider doing something like implementing Space Invaders. Ultimately, I kind of want to run a simple simulated CP/M system. We’ll see how it goes: stay tuned.