Introduction to Computer Data Representation

We start with the basic ideas of "numbers" and "counting" and how the concepts and requirements differ with different levels of technical and administrative sophistication. This is followed by a brief summary of the development of calculating devices, to the structure of the "von Neumann" computer. Finally, we introduce the requirements of a computer, the importance of memory and an overview of data storage within that memory.

The initial idea of "number" leads quickly to the need to represent numbers and then manipulate numbers. We emphasise the representation as the terms of polynomial in some base and especially "binary numbers" (to base 2) and "decimal numbers" (to base 10). This leads into conversion between bases and the representation of fractions in binary.

Although the "natural" integers 1,2,3,. . .) are adequate for many, everyday, purposes they do not handle concepts such as debts; the representation must extended to handle negative values. This chapter therefore introduces the three conventional forms of signed binary representation (sign and magnitude, ones complement and two complement). Finally, it describes some other important number representations, especially mixed base (for non-metric measures), but also the more-specialised redundant codings, Gray codes and Zeckendorf representations.

Given that quantities may be represented as bit patterns within the computer, how may these patterns be manipulated to achieve useful results? We look first at the "basic" operations of addition and subtraction in the various binary number representations, extending to addition of multiple-precision values and decimal addition. Then we examine the logical operations, where the bits are "bits", with no numerical significance. Operations here include AND, OR, NOT, XOR, shifting of various types, bit-field operations and, finally, parity.

This chapter firstly extends the earlier principles of addition to provide faster adders. It then describes the underlying principles of binary multiplication and division, and especially techniques for fast operations.

This chapter extends the earlier representations of integers to the equivalent of the real numbers of scientific calculation. It discusses the basic ideas, especially with reference to the IEEE 754 standard, and contrasting with descriptions of the IBM S/360 and Burroughs B6700 representations. There is extensive discussion of the requirements of ideal floating-point representations and the failings of practical implementations. Special mention is made of the requirements of range, precision and rounding. It concludes with examples of straight-forward calculations which can easily overwhelm many floating-point systems.

Some types of calculation emphasise multiplication and division over addition and subtraction. Representing numbers as their logarithms accelerates multiplication and division, but slightly complicates addition and subtraction. This chapter gives a brief overview of logarithmic representations and their arithmetic.

Characters are the most-visible aspect of computing. This chapter outlines the development of the EBCDIC codes (from card code), and ASCII (initially from paper tape), and the extension of these codes to include a full range of alphabets, to give UNICODE. Other topics include the collection of characters into text strings, and especially the problems of transmitting binary data over systems designed for handling text. Thus it describes UTF-8 and UTF-7 coding, as well as "punycode", for encoding Internet domain names with arbitrary alphabets.

Text compression requires numbers to represented as compactly as possible, especially the more-frequent values. This chapter describes various compact representations, and especially the "Universal Codes" to represent arbitrarily large values. Many of these codes are seldom mentioned in general literature.

Much computer data is prone to errors, especially when transmitted in space (or in time, as in data storage). The corresponding need for error detection and correction has been recognised from the very beginning of electrical computation. Error correction is a large and complex subject which is just touched-on here, but error detection is a much simpler, but seldom discussed subject and is the main emphasis of this chapter. After a brief mention of parity checks in textual data transmission, the emphasis is on checksums for verifying strings of decimal digits. Check-digit algorithms include the Luhn, those used in ISBN codes, and the Verhoe and Damm checks, both based on advanced number theory. The chapter concludes with discussion of the more-powerful message checksums, especially those of Fletcher and Adler, and the Cyclic Redundancy checks.

This chapter contains a variety of topics, especially a history of numbers, justification for binary bits, good number representations, the history of `word', `bit' and `byte', a history of character codes, a variety of decimal codes and Roman numbers.