Group Code Recording
Encyclopedia
In computer science
, group code recording (GCR) refers to several distinct but related encoding methods for magnetic media. The first, used in 6250 cpi magnetic tape
, is an error-correcting code combined with a run length limited
encoding scheme. The others are different floppy disk
encoding methods used in some microcomputers until the late 1980s.
. Prior to 6250 cpi tapes, 1600 cpi tapes satisfied these constraints using a technique called phase encoding
, which was only 50% efficient. For 6250 GCR tapes, a (0,2)RLL
code is used. This code requires five bits to be written for every four bits of data. The code is structured so that no more than two zero bits (which are represented by lack of a flux reversal) can occur in a row, either within a code or between codes, no matter what the data was. This RLL code is applied independently to the data going to each of the 9 tracks.
Of the 32 5-bit patterns, 8 begin with two consecutive zero bits, 6 others end with two consecutive zero bits, and one more (10001) contains three consecutive zero bits. Removing the all-ones pattern (11111) from the remainder leaves 16 suitable code words.
The 6250 GCR RLL code:
11 of the nibbles (other than xx00 and 0001) have their code formed by prepending the complement of the msbit; i.e. abcd is encoded as a̅abcd. The other 5 values are assigned codes beginning with 11. Nibbles of the form ab00 have codes 11baa̅, i.e. the bit reverse of the code for ab11. The code 0001 is assigned the remaining value 11011.
Because of the extremely high density of 6250 cpi tape, the RLL code is not sufficient to ensure reliable data storage. On top of the RLL code, an error-correcting code called the Optimal Rectangular Code (ORC) is applied. This code is a combination of a parity
track and polynomial
code similar to a CRC
, but structured for error correction rather than error detection. For every 7 bytes written to the tape (before RLL encoding), an 8th check byte is calculated and written to the tape. When reading, the parity is calculated on each byte and exclusive-or'd with the contents of the parity track, and the polynomial check code calculated and exclusive-or'd with the received check code, resulting in two 8-bit syndrome words. If these are both zero, the data is error free. Otherwise, error-correction logic in the tape controller corrects the data before it is forwarded to the host. The error correcting code is able to correct any number of errors in any single track, or in any two tracks if the erroneous tracks can be identified by other means.
IBM documents refer to the error correcting code itself as "group coded recording". However, GCR has come to refer to the recording format of 6250 cpi tape as a whole, and later to formats which use similar RLL codes without the error correction code.
drives have physical limits on the spacing of flux reversals (also called transitions, represented by 1 bits).
For the Apple II
floppy drive, Steve Wozniak
invented a floppy controller which (along with the drive itself) imposed two constraints
The simplest scheme to ensure compliance with these limits is to record an extra "clock" transition between each data bit. This scheme is called FM (Frequency Modulation) or "4 and 4", and allows only 10 256-byte sectors per track to be recorded on a single-density 5¼ floppy.
Wozniak realized that a more complex encoding scheme would allow each 8-bit byte on disk to hold 5 bits of useful data rather than 4 bits. This is because there are 34 bytes which have the top bit set and no two zero bits in a row. This encoding scheme became known as "5 and 3" encoding, and allowed 13 sectors per track; it was used for Apple DOS
3.1, 3.2, and 3.2.1, as well as for the earliest version of Apple CP/M. Later, the design of the floppy drive controller was modified to allow a byte on disk to contain exactly one pair of zero bits in a row. This allowed each 8-bit byte to hold 6 bits of useful data, and allowed 16 sectors per track. This scheme is known as "6 and 2", and was used on Apple Pascal
, Apple DOS 3.3 and ProDOS
, and later on the 400K and 800K 3½ disks on the Macintosh and Apple II
. Apple did not originally call this scheme "GCR", but the term was later applied to it to distinguish it from IBM PC floppies which used the MFM
encoding scheme.
Independently, Commodore Business Machines
created a Group Code Recording scheme for their Commodore 2040 floppy disk drive (launched in the spring of 1979). The relevant constraint on the 2040 drive was that no more than two zero bits could occur in a row, with no special constraint on the first bit in a byte. This allowed the use of a scheme similar to that used in 6250 tape drives. Every 4 bits of data are translated into 5 bits on disk, according to the following table:
Note no code starts with two zero bits, nor ends with two zero bits. This ensures that regardless of the input data, the encoded data will never contain more than two zero bits in a row. Also note that with this encoding not more than eight one bits in a row are possible. Therefore Commodore used sequences of ten or more one bits in a row as synchronization mark.
Partially because of this more efficient scheme, Commodore was able to fit 170KB on a standard single-density floppy, where Apple fit 140K (6 and 2) or 114K (5 and 3) and an FM-encoded floppy held only 88K.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, group code recording (GCR) refers to several distinct but related encoding methods for magnetic media. The first, used in 6250 cpi magnetic tape
Magnetic tape
Magnetic tape is a medium for magnetic recording, made of a thin magnetizable coating on a long, narrow strip of plastic. It was developed in Germany, based on magnetic wire recording. Devices that record and play back audio and video using magnetic tape are tape recorders and video tape recorders...
, is an error-correcting code combined with a run length limited
Run Length Limited
Run length limited or RLL coding is a line coding technique that is used to send arbitrary data over a communications channel with bandwidth limits. This is used in both telecommunication and storage systems which move a medium past a fixed head. Specifically, RLL bounds the length of stretches ...
encoding scheme. The others are different floppy disk
Floppy disk
A floppy disk is a disk storage medium composed of a disk of thin and flexible magnetic storage medium, sealed in a rectangular plastic carrier lined with fabric that removes dust particles...
encoding methods used in some microcomputers until the late 1980s.
GCR for 9-track reel-to-reel tape
In order to reliably read and write to magnetic tape, several constraints on the signal to be written must be followed. The first is that two adjacent flux reversals must be separated by a certain distance on the media. The second is that there must be a flux reversal often enough to keep the reader's clock in phase with the written signal; that is, the signal must be self-clockingSelf-clocking signal
In telecommunications and electronics, a self-clocking signal is one that can be decoded without the need for a separate clock signal or other source of synchronization...
. Prior to 6250 cpi tapes, 1600 cpi tapes satisfied these constraints using a technique called phase encoding
Manchester code
In telecommunication and data storage, Manchester code is a line code in which the encoding of each data bit has at least one transition and occupies the same time...
, which was only 50% efficient. For 6250 GCR tapes, a (0,2)RLL
Run Length Limited
Run length limited or RLL coding is a line coding technique that is used to send arbitrary data over a communications channel with bandwidth limits. This is used in both telecommunication and storage systems which move a medium past a fixed head. Specifically, RLL bounds the length of stretches ...
code is used. This code requires five bits to be written for every four bits of data. The code is structured so that no more than two zero bits (which are represented by lack of a flux reversal) can occur in a row, either within a code or between codes, no matter what the data was. This RLL code is applied independently to the data going to each of the 9 tracks.
Of the 32 5-bit patterns, 8 begin with two consecutive zero bits, 6 others end with two consecutive zero bits, and one more (10001) contains three consecutive zero bits. Removing the all-ones pattern (11111) from the remainder leaves 16 suitable code words.
The 6250 GCR RLL code:
| Nibble Nibble In computing, a nibble is a four-bit aggregation, or half an octet... |
Code | Nibble | Code |
|---|---|---|---|
| 0000 | 11001 | 1000 | 11010 |
| 0001 | 11011 | 1001 | 01001 |
| 0010 | 10010 | 1010 | 01010 |
| 0011 | 10011 | 1011 | 01011 |
| 0100 | 11101 | 1100 | 11110 |
| 0101 | 10101 | 1101 | 01101 |
| 0110 | 10110 | 1110 | 01110 |
| 0111 | 10111 | 1111 | 01111 |
11 of the nibbles (other than xx00 and 0001) have their code formed by prepending the complement of the msbit; i.e. abcd is encoded as a̅abcd. The other 5 values are assigned codes beginning with 11. Nibbles of the form ab00 have codes 11baa̅, i.e. the bit reverse of the code for ab11. The code 0001 is assigned the remaining value 11011.
Because of the extremely high density of 6250 cpi tape, the RLL code is not sufficient to ensure reliable data storage. On top of the RLL code, an error-correcting code called the Optimal Rectangular Code (ORC) is applied. This code is a combination of a parity
Parity bit
A parity bit is a bit that is added to ensure that the number of bits with the value one in a set of bits is even or odd. Parity bits are used as the simplest form of error detecting code....
track and polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
code similar to a CRC
Cyclic redundancy check
A cyclic redundancy check is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data...
, but structured for error correction rather than error detection. For every 7 bytes written to the tape (before RLL encoding), an 8th check byte is calculated and written to the tape. When reading, the parity is calculated on each byte and exclusive-or'd with the contents of the parity track, and the polynomial check code calculated and exclusive-or'd with the received check code, resulting in two 8-bit syndrome words. If these are both zero, the data is error free. Otherwise, error-correction logic in the tape controller corrects the data before it is forwarded to the host. The error correcting code is able to correct any number of errors in any single track, or in any two tracks if the erroneous tracks can be identified by other means.
IBM documents refer to the error correcting code itself as "group coded recording". However, GCR has come to refer to the recording format of 6250 cpi tape as a whole, and later to formats which use similar RLL codes without the error correction code.
GCR for floppy disks
Like magnetic tape drives, floppy diskFloppy disk
A floppy disk is a disk storage medium composed of a disk of thin and flexible magnetic storage medium, sealed in a rectangular plastic carrier lined with fabric that removes dust particles...
drives have physical limits on the spacing of flux reversals (also called transitions, represented by 1 bits).
For the Apple II
Apple II
The Apple II is an 8-bit home computer, one of the first highly successful mass-produced microcomputer products, designed primarily by Steve Wozniak, manufactured by Apple Computer and introduced in 1977...
floppy drive, Steve Wozniak
Steve Wozniak
Stephen Gary "Woz" Wozniak is an American computer engineer and programmer who founded Apple Computer, Co. with Steve Jobs and Ronald Wayne...
invented a floppy controller which (along with the drive itself) imposed two constraints
- Between any two one bits, there may be a maximum of one zero bit.
- Each 8-bit byte must start with a one bit.
The simplest scheme to ensure compliance with these limits is to record an extra "clock" transition between each data bit. This scheme is called FM (Frequency Modulation) or "4 and 4", and allows only 10 256-byte sectors per track to be recorded on a single-density 5¼ floppy.
Wozniak realized that a more complex encoding scheme would allow each 8-bit byte on disk to hold 5 bits of useful data rather than 4 bits. This is because there are 34 bytes which have the top bit set and no two zero bits in a row. This encoding scheme became known as "5 and 3" encoding, and allowed 13 sectors per track; it was used for Apple DOS
Apple DOS
Apple DOS refers to operating systems for the Apple II series of microcomputers from late 1978 through early 1983. Apple DOS had three major releases: DOS 3.1, DOS 3.2, and DOS 3.3; each one of these three releases was followed by a second, minor "bug-fix" release, but only in the case of Apple DOS...
3.1, 3.2, and 3.2.1, as well as for the earliest version of Apple CP/M. Later, the design of the floppy drive controller was modified to allow a byte on disk to contain exactly one pair of zero bits in a row. This allowed each 8-bit byte to hold 6 bits of useful data, and allowed 16 sectors per track. This scheme is known as "6 and 2", and was used on Apple Pascal
Apple Pascal
Apple Pascal was a language and operating system based on the UCSD Pascal system.Apple Pascal refers to an operating system for the Apple II family of computers released in August 1979 between the Apple DOS 3.2 and 3.3 versions. The system was included as part of a software/hardware package adding...
, Apple DOS 3.3 and ProDOS
ProDOS
ProDOS was the name of two similar operating systems for the Apple II series of personal computers. The original ProDOS, renamed ProDOS 8 in version 1.2, was the last official operating system usable by all Apple II series computers, and was distributed from 1983 to 1993...
, and later on the 400K and 800K 3½ disks on the Macintosh and Apple II
Apple II
The Apple II is an 8-bit home computer, one of the first highly successful mass-produced microcomputer products, designed primarily by Steve Wozniak, manufactured by Apple Computer and introduced in 1977...
. Apple did not originally call this scheme "GCR", but the term was later applied to it to distinguish it from IBM PC floppies which used the MFM
Modified Frequency Modulation
Modified Frequency Modulation, commonly MFM, is a line coding scheme used to encode the actual data-bits on most floppy disk formats, hardware examples include Amiga, most CP/M machines as well as IBM PC compatibles. Early hard disk drives also used this coding.MFM is a modification to the original...
encoding scheme.
Independently, Commodore Business Machines
Commodore International
Commodore is the commonly used name for Commodore Business Machines , the U.S.-based home computer manufacturer and electronics manufacturer headquartered in West Chester, Pennsylvania, which also housed Commodore's corporate parent company, Commodore International Limited...
created a Group Code Recording scheme for their Commodore 2040 floppy disk drive (launched in the spring of 1979). The relevant constraint on the 2040 drive was that no more than two zero bits could occur in a row, with no special constraint on the first bit in a byte. This allowed the use of a scheme similar to that used in 6250 tape drives. Every 4 bits of data are translated into 5 bits on disk, according to the following table:
|
|
Note no code starts with two zero bits, nor ends with two zero bits. This ensures that regardless of the input data, the encoded data will never contain more than two zero bits in a row. Also note that with this encoding not more than eight one bits in a row are possible. Therefore Commodore used sequences of ten or more one bits in a row as synchronization mark.
Partially because of this more efficient scheme, Commodore was able to fit 170KB on a standard single-density floppy, where Apple fit 140K (6 and 2) or 114K (5 and 3) and an FM-encoded floppy held only 88K.
See also
- Modified Frequency ModulationModified Frequency ModulationModified Frequency Modulation, commonly MFM, is a line coding scheme used to encode the actual data-bits on most floppy disk formats, hardware examples include Amiga, most CP/M machines as well as IBM PC compatibles. Early hard disk drives also used this coding.MFM is a modification to the original...
(MFM) - Run Length LimitedRun Length LimitedRun length limited or RLL coding is a line coding technique that is used to send arbitrary data over a communications channel with bandwidth limits. This is used in both telecommunication and storage systems which move a medium past a fixed head. Specifically, RLL bounds the length of stretches ...
(RLL) - Eight-to-Fourteen ModulationEight-to-Fourteen ModulationEight-to-fourteen modulation is a data encoding technique – formally, a channel code – used by compact discs and pre-Hi-MD MiniDiscs. EFMPlus is a related code, used in DVDs and SACDs. EFM and EFMPlus were both invented by Kees A...
(EFM) - Error-correcting code
- 8b/10b encoding8B/10B encodingIn telecommunications, 8b/10b is a line code that maps 8-bit symbols to 10-bit symbols to achieve DC-balance and bounded disparity, and yet provide enough state changes to allow reasonable clock recovery. This means that the difference between the count of 1s and 0s in a string of at least 20 bits...
External links
- The PC Guide Frequency Modulation
- The Gallery of Old Iron A comment on the origin of the name "Group Coded Recording".