Common methods of transmitting digital data through an extremely noisy audio signal? I am developing software for transmitting data from a computer to a mobile device using audio. Specifically, from the computer's speaker to the device's microphone. (I am developing both the sender and the receiver software.) This is one channel, and the sample rate is a standard 44.1Khz. It needs to be VERY resilient to noise - it will be used in environments with street noise, people talking, background music, etc., which may be 10dB louder than the signal itself.

Knowing almost nothing about DSP, thus far I have apparently implemented frequency-division multiplexed on-off keying, without realizing it until now :) Basically each of 96 frequencies corresponds to a bit, and on the receiving end, if the frequency is present, the bit is on. I then use some custom error correction code to whittle those 96 bits down to 8 very reliable bits.

My system works very well and is very robust, but unfortunately has an EXTREMELY low data rate (~80 bits/sec). I have some ideas about how to improve bandwidth, like using more than 96 frequencies, and using the phase component to encode additional data. Also it appears I should look into frequency-shift keying and phase-shift keying.

So - my question is simply this:

What are the options for encoding data in a noisy broadcast audio signal, and what kind of bandwidth and error rates can be expected with each technique?
The scheme you are using is called On/Off Keying.  It is not terribly efficient, but it is simple and gets the job done.

When you say that the signal is 10 dB below the noise floor I suspect what you mean is that if you add up all the signal energy and all of the noise from 0.3 - 14 kHz the signal is 10 dB weaker, but that the signal uses a much narrower frequency range, making the signal stronger at very specific frequencies.  If it wasn't, you would not be getting reliable data transmission without doing long synchronous averaging, and it sounds like you aren't.

There are a number of different ways you could do this.  The state of the art would be to use an OFDM signal in the 17-21 kHz band.  A much simpler but not as efficient way to go (but still much more efficient than your OOK) would be to use a QPSK signal in the 17-21 kHz band.  If you have enough transmission power you could modify it to 8-PSK or 16-QAM for higher throughput.  Since it sounds like the transmission power is more of a limitation than the bandwidth (you can get a lot more data through 4 kHz of bandwidth than 80 bits/s), I would add a forward error correction (FEC) code to the data stream.

With QPSK you can get (ignoring the potential reduction in throughput from the error correction code) 1 bit/s/Hz, so you would have an upper limit of 4 kbits/s.  With 8-PSK it would be 6 kbits/s, and with 16-QAM it is 8 kbits/s.  The price of going with the higher data rates is that you are more likely to have errors.

The data rate for OFDM is more complicated.  Given your level of DSP knowledge I would go with QPSK, and then modify from there if needed.  It sounds like you would be thrilled with anything even close to 4 kbits/s, so that should be plenty good enough.