Of all the various projects I've worked on in my life at the BBC, the one I'm most proud of is the transform PAL decoder. On this page I'll try to describe a little of its history and how it works, and link to any related info I discover. Please note that all images on this page are ©BBC.
Before getting into the details of how the transform PAL decoder works, here's a few example pictures to show what it does. They were prepared by Steve Roberts of the Dr. Who restoration team to help decide whether to remaster the story "Remembrance of the Daleks". The pictures are grossly enlarged and over-saturated, so they aren't representative of a normal TV picture.
These two pictures show how effective the transform PAL decoder is at removing cross-colour. The first picture shows how fine detail (such as the mesh on a dalek) can cause cross colour, even with a top-quality professional decoder. The second picture is from the transform PAL decoder — cross-colour is almost entirely exterminated.
This pair of highly magnified pictures show the other form of cross talk in a colour composite system — cross-luminance, or dot crawl. This occurs where a decoder does not completely remove the modulated chrominance from the luminance signal, leaving a moving pattern of fine dots. This is most commonly seen on the edges of coloured objects, such as on the computer display in this scene from "Remembrance of the Daleks". As before, the transform decoder knocks spots off the competition.
This last pair of pictures shows an example of the transform decoder not completely removing cross colour. The first picture shows cross colour on the clipboard edge, the fine text, the typewriter lever and the girl's jersey. The transform decoder (second picture) is a lot better, but there is still some colour on the text which I think shouldn't be there.
The BBC Research Department at Kingswood Warren had a long history of PAL decoder inventions. Many of these, such as "Weston Clean PAL" and "Extended PAL", achieve clean separation of luminance and chrominance by using a modified encoder to make a PAL-like signal that can be decoded cleanly by a matching decoder. The more general problem of cleanly decoding signals from any normal PAL encoder is much harder to solve.
Over the years, I tried a few ideas of my own, often in friendly rivalry with John Drewery — his mathematical rigour against my more experimental approach. Most of these, such as adding motion compensation to a multi-field filter, offered a small improvement, but not enough to justify their complexity. Then, during the Christmas holiday at the end of 1999, I had a radically different idea.
In the PAL (or NTSC) colour coding system, chrominance information is modulated onto a carrier before being added to the luminance signal. It occurred to me that the modulated chrominance is a double side band signal whose spectrum should be symmetrical about the colour sub-carrier. If one could remove any spectrum that is not symmetrical about the carrier, then one could extract the modulated chrominance from the composite video signal.
I thought about this idea for some weeks, unable to decide if it was just an interesting aside, or if it had any real potential. Ultimately, I realised that no amount of thinking would answer the question, so I had to try it out. I started work on a computer simulation (using software tools I'd previously developed) in my lunchtimes and after work. I was utterly astonished when my first simulations delivered cleaner decoding than I'd ever seen before.
In order to explain how the decoder works, I first need to explain a bit about 3-dimensional spectra of video signals. When talking about a frequency, such as PAL colour sub-carrier, it's common to refer to its "signal frequency" of 4.43361875 MHz. However, when displayed on a monitor a video signal becomes a spatio-temporal frequency with three components: horizontal frequency m, vertical frequency n & temporal frequency f.
Consider a stationary image of some striped material. If the stripes are vertical, then scanning the image horizontally produces a cyclic variation in brightness. The fineness of the pattern can be expressed as a number of cycles per active picture width, or c/apw, which is the unit used for m. Similarly, if the stripes are horizontal, we have a vertical frequency n measured in cycles per active picture height, c/aph.
Now consider a video image of a moving piece of striped material. If we fixate on one part of the screen we get a cyclic variation in brightness as the pattern moves past. This can be expressed as a temporal frequency f in Hz. Note that the horizontal and vertical frequencies of the image haven't changed now it's moving, but it's acquired a temporal frequency.
Returning to the PAL colour sub-carrier, its frequency was chosen to minimise its visibility on the screens of black & white TVs. It has a "quarter line offset" which shifts the phase of its pattern by a quarter of a cycle each field line, so it has 72 cycles in one active field of 288 lines, giving a vertical frequency n of 72 c/aph. As there are 625 lines in a frame, and 625 mod 4 = 1, this quarter line offset also produces a retardation of a quarter cycle per frame period. The "25 Hz offset" adds one cycle per frame period, so subtracting the quarter cycle retardation gives an overall shift of ¾ cycles per frame period, a temporal frequency f of 18.75 Hz.
Television is a sampled system. In most PAL systems it is sampled at 50 fields per second, with 288 active lines per field (ignoring the half lines at the top and bottom of the picture). It is also interlaced, with two fields per frame. Nyquist sampling theory teaches us that the spectrum of a sampled signal has an infinite number of repeats, at multiples of the sampling frequency. Hence, the spectrum of our interlaced TV signal repeats vertically at multiples of 576 c/aph, temporally at multiples of 50 Hz, and vertical-temporally at multiples of (288 c/aph, 25 Hz). Hence the sub-carrier frequency (72 c/aph, 18.75 Hz) has a repeat at (-216 c/aph, -6.25 Hz).
One last complication of PAL is that which gives it its name, the V-axis switch. This can be thought of as a modulation of the V component by a signal that alternates every field line. This modulation has frequency (144 c/aph, -12.5 Hz) and shifts the V sub-carrier from (72 c/aph, 18.75 Hz) to (216 c/aph, 6.25 Hz), which has a repeat at (-72 c/aph, -18.75 Hz).
The figure above shows the spatial frequency "region of support" for one field of a PAL signal sampled at four times the colour sub-carrier frequency. (This sampling frequency is used in the D3 videotape system and in the transform decoder.) It shows horizontal frequencies from -2fsc to +2fsc and vertical frequencies from -144 c/aph to +144 c/aph. The U colour sub-carrier is at (fsc, 72 c/aph) and the V sub-carrier is at (fsc, -72 c/aph) because of the V-axis switch, as discussed above. However, reflections of these carriers are also present at (-fsc, -72 c/aph) and (-fsc, 72 c/aph).
Now, as every real signal has both positive and negative frequencies, which are of equal amplitude, when that signal is used to modulate a carrier it produces frequencies on both sides of that carrier. In the figure, X represents a colour signal whose baseband U frequency is (0.25fsc, -36 c/aph). When modulated onto the U sub-carrier it appears at (1.25fsc, 36 c/aph). Of course, the baseband signal also has a negative frequency component at (-0.25fsc, 36 c/aph), which, when modulated onto the U sub-carrier appears at (0.75fsc, 108 c/aph) and is shown as X'. Note that these signals will also be modulated onto the reflection of the U sub-carrier, but these have not been shown on the diagram.
If we compare the amplitudes of X and X', we will find that they are the same, as they derive from positive and negative frequency components of the same baseband signal. Whilst it is possible that the unmodulated luminance signal could contain frequency components of equal amplitude at X and X', it is unlikely. This allows us to extract the modulated U signal by removing anything that is not symmetric about the U sub-carrier.
X could instead be a V signal with a baseband frequency of (0.25fsc, 108 c/aph). In this case it is modulated onto the V carrier, but X' is still its reflection about the V carrier, as shown by the longer arrows (remembering that when we go off the bottom of the diagram, we reappear at the top). Furthermore, X' is also the reflection of X in the negative frequency U and V carriers. Hence, enforcing symmetry about one carrier will enforce symmetry about them all.
My first attempts at computer simulation of a PAL decoder using this idea used two-dimensional Fourier transforms operating on single fields, as discussed above. The results were encouraging, but it was clear that there were occasions when the spectrum of the luminance signal was sufficiently symmetric about colour sub-carrier to be mistaken for chrominance. Extending the idea to three dimensions was an obvious development.
This diagram shows a vertical-temporal slice through the "region of support" at a horizontal frequency of fsc. The U sub-carrier is at (fsc, 72 c/aph, 18.75 Hz) and the V sub-carrier is offset by the V-axis switch to (fsc, 216 c/aph, 6.25 Hz). Note that the reflected U carrier is at (-fsc, -72 c/aph, -18.75 Hz) so does not appear on this diagram (because it's a slice at +fsc). Instead we have reflections of the carriers from -fsc: U at (fsc, -216 c/aph, -6.25 Hz) and V at (fsc, -72 c/aph, -18.75 Hz). These are also the locations of the repeats caused by interlace, which offsets the original carriers by (-288 c/aph, -25 Hz).
Once again we have a pair of frequencies X and X' that correspond to a positive-negative frequency pair of baseband colour signals, and their interlace duplicates. And once again, this pair of signals is symmetric about all the aliases and reflections of the colour sub-carriers.
This block diagram shows the principle behind a "complementary" PAL decoder. Some form of filter is used to extract the modulated chrominance from a PAL signal. Subtracting this chrominance from a suitably delayed PAL signal then yields luminance, whilst demodulating it with U and V sub-carriers yields the U & V signals. The decoder is called complementary because, before demodulation, the modulated chrominance is the complement of the luminance. Adding them together gives the original PAL signal.
Decoders like this are not widely used, as better subjective results can be obtained by using separate filters for chrominance and luminance, each optimised to give the best looking signals.
This diagram shows how a Fourier transform based filter can be used in a complementary PAL decoder. We've introduced a lot of extra complexity. Firstly the data is rearranged into blocks, then a windowing function is applied to reduce the effect of block edges on the Fourier transform, then we take the Fourier transform of each block. The "transform domain filter" does something to the blocks in the frequency domain, after which they are transformed back to the time domain, have an inverse window function applied to undo the effect of the window function, and finally the data is rearranged into the correct order.
Using Fourier transforms in this way is a lot of trouble to go to, but it gives us one enormous benefit. The filtering of each block can easily depend on the spectrum of that block. So, in the BBC transform PAL decoder, each frequency in the block is compared with its reflection about the colour sub-carrier frequency, and if the magnitudes are too dissimilar the pair of frequencies is rejected.
Dividing the picture into blocks and processing each one separately is potentially very risky. If two adjacent blocks are treated very differently, then block boundaries might be visible on the final picture. To avoid this we use overlapping blocks: each block starts halfway through the previous one, horizontally, vertically and temporally. When recombining the blocks we "cross fade" from one to the next, which is easily achieved by modifying the inverse window function.
Using computer simulations of the transform PAL decoder algorithm I'd been able to show that three-dimensional processing was vastly better than two-dimensional, and I'd been able to experiment with different block sizes, window functions and so on. However, I'd not been able to process more than a few seconds of carefully chosen test material. I did wonder if a software version of the decoder might have an application in extracting high quality stills from composite video, but it was clear that real-time hardware would be needed to meet the requirements of our most likely "customer", the BBC archives.
We gave demonstrations of the computer simulation results to various interested parties, and more publicly at the departmental open days. However, no manufacturer was interested, mainly because of the lack of an NTSC version (more about that later). Eventually it was decided that we should build a small number of units for BBC use, and Richard Russell was asked to design the hardware. Suddenly I had to explain the algorithm in a lot more detail than before, which put me on the spot. However, there's nothing like explaining something to another person for revealing your own lack of understanding. Only then did I really begin to understand how PAL works. "Science owes more to the steam engine than the steam engine owes to science."
During Richard's development of the decoder he came up with several good ideas to reduce the amount of processing required. I tried most of these in simulation, and usually got a useful speed up of the simulation as well! For example, ¾ of the data can be thrown away after the incoming signal has been horizontally Fourier transformed. We're only interested in what happens around fsc, and because we've started with a real signal, the negative frequency Fourier samples are just complex conjugates of the positive frequency ones and so can be recreated later, just before the final inverse FT.
A harder to understand modification was devised to reduce the 2:1 overhead of processing an interlaced signal with orthogonal Fourier transforms. Instead of inserting lines of zero to make a non-interlaced signal at twice the data rate, as had been done in simulation, we skewed the block structure by one line every field, and adjusted the sub-carrier positions to match. This does have some side effects — what was a stationary object may now be moving through a block, or from one block to the next, and so could acquire some moving artefacts. I think I may have seen this effect on a few, very difficult, test sequences.
As we have seen, the effect of the PAL V-axis switch is to offset the V sub-carrier from the U sub-carrier by (144 c/aph, -12.5 Hz). In NTSC there is no V-axis switch, and so the I & Q components are modulated onto exactly the same sub-carrier frequency.
Consider the attractive deckchair material shown above. These colours have the following YIQ values:
The thing to note in this table is that I and Q are in quadrature — their amplitudes are square waves 90° apart. A square wave closely approximates to a sum of sine waves with odd harmonics, so we can write:
I = kI[sin(ωt) + sin(3ωt)/3 + sin(5ωt)/5 + ...]
Q = kQ[sin(ωt + π/2) + sin(3ωt + π/2)/3 + sin(5ωt + π/2)/5 + ...]
I = kI[sin(ωt) + sin(3ωt)/3 + sin(5ωt)/5 + ...]
Q = kQ[cos(ωt) + cos(3ωt)/3 + cos(5ωt)/5 + ...]
When these signals are quadrature modulated by the colour sub-carriers, they are multiplied by sine and cosine waves at the sub-carrier frequency:
I = kIsin(θt)[sin(ωt) + sin(3ωt)/3 + sin(5ωt)/5 + ...]
Q = kQcos(θt)[cos(ωt) + cos(3ωt)/3 + cos(5ωt)/5 + ...]
I = kI[sin(θt)sin(ωt) + sin(θt)sin(3ωt)/3 + sin(θt)sin(5ωt)/5 + ...]
Q = kQ[cos(θt)cos(ωt) + cos(θt)cos(3ωt)/3 + cos(θt)cos(5ωt)/5 + ...]
Applying some trigonometric identities we get:
I = kI[cos(θt-ωt)/2 - cos(θt+ωt)/2 + cos(θt-3ωt)/6 - cos(θt+3ωt)/6 + cos(θt-5ωt)/10 - cos(θt+5ωt)/10 + ...]
Q = kQ[cos(θt-ωt)/2 + cos(θt+ωt)/2 + cos(θt-3ωt)/6 + cos(θt+3ωt)/6 + cos(θt-5ωt)/10 + cos(θt+5ωt)/10 + ...]
Finally, the modulated I & Q signals are added together, making a single modulated chrominance signal to be added to the luminance:
C = (kQ+kI)[cos(θt-ωt)/2 + cos(θt-3ωt)/6 + cos(θt-5ωt)/10 + ...] + (kQ-kI)[cos(θt+ωt)/2 + cos(θt+3ωt)/6 + cos(θt+5ωt)/10 + ...]
Now let's consider what this equation represents. The first group of terms are the lower sideband of the signal, and the second group are the upper sideband. Note that they are of different amplitudes, as
(kQ+kI) != (kQ-kI). This will completely defeat any attempt to extract chrominance by looking for symmetry!
Unfortunately, this problem can also occur in PAL. Fortunately, it is very much less likely. Although U & V are modulated onto the same horizontal frequency, the V-axis switch ensures that their sub-carriers have different vertical and temporal frequencies. Hence this problem can only occur if the baseband chrominance has a vertical-temporal frequency of (72 c/aph, -6.25 Hz) — half the V-axis switch frequency. In this case, the modulated U and V signals finish up at the same frequency and could interfere to make asymmetric sidebands. In NTSC the problem can occur at any vertical-temporal frequency.
Disclaimer: any opinions expressed in the above are my personal views and not those of the BBC.