Mathematics for Digital Science 2
Description
Over the past century, advancements in computer science have consistently resulted from extensive mathematical work. Even today, innovations in the digital domain continue to be grounded in a strong mathematical foundation. To succeed in this profession, both today's students and tomorrow's computer engineers need a solid mathematical background.
The goal of this book series is to offer a solid foundation of the knowledge essential to working in the digital sector. Across three volumes, it explores fundamental principles, digital information, data analysis, and optimization. Whether the reader is pursuing initial training or looking to deepen their expertise, the Mathematics for Digital Science series revisits familiar concepts, helping them refresh and expand their knowledge while also introducing equally essential, newer topics.
More details
Other editions
Additional editions
Content
Preface xi
Chapter 1 Representation of Numbers 1
1.1 Representation of numbers 2
1.1.1 Position numbering 2
1.1.2 The binary system 3
1.1.3 Octal system and hexadecimal system 6
1.2 Representation of numbers in a machine 8
1.2.1 Machine representation of negative numbers 8
1.2.2 Representation of rational numbers 12
Chapter 2 Media Representation 17
2.1 Character coding 17
2.2 Image coding 23
2.2.1 Representation of digital colors 23
2.2.2 Scanning an image 24
2.2.3 Image quality 24
2.3 Sound coding 26
2.4 Video coding 28
2.5 Tagging codes 29
2.5.1 Figures 29
2.5.2 Bank cards 30
2.5.3 Barcodes 32
2.5.4 QR codes 34
Chapter 3 Signals and Systems 47
3.1 Characteristics and varieties 47
3.1.1 Introduction 47
3.1.2 Periodicity 49
3.1.3 Noise 50
3.2 Fourier analysis 51
3.2.1 Fourier series expansion 51
3.2.2 Examples 52
3.2.3 Special cases 55
3.2.4 Other development writing 55
3.2.5 Power 56
3.3 Dirac distribution 58
3.4 Convolution 62
3.4.1 Definition 62
3.4.2 Dirac distribution and convolution 64
Chapter 4 z-transforms Fourier Transforms and Laplace Transforms 67
4.1 z-transform 68
4.1.1 Definitions and main results 68
4.1.2 Application to discrete systems 70
4.2 Fourier transform 73
4.2.1 Periodic signals 73
4.2.2 Non-periodic signals 74
4.2.3 Main properties of Fourier transforms 79
4.2.4 Application to analog signals and systems 82
4.2.5 Transfer function 86
4.2.6 Autocorrelation and intercorrelation of signals 88
4.3 Discrete Fourier transform and fast Fourier transform 91
4.3.1 Discrete Fourier transform 91
4.3.2 Fast Fourier transform (FFT) 95
4.4 Laplace transform 101
4.4.1 Definition 101
4.4.2 Properties 102
4.4.3 Differential equation 103
4.4.4 Convolution product 104
Chapter 5 Digitizing an Analog Signal 107
5.1 Introduction 107
5.2 Sampling 108
5.3 Quantization 112
5.4 Coding 116
Chapter 6 Modulation 119
6.1 Types of modulation 119
6.2 Amplitude modulation 121
6.2.1 Principle 121
6.2.2 Frequency space 123
6.2.3 Signal strength 124
6.2.4 Overmodulation 125
6.2.5 Demodulation 126
6.2.6 Single sideband 127
6.2.7 Modulation of a binary signal 127
6.3 Frequency modulation 130
6.3.1 Principle 130
6.3.2 Case of a sinusoidal signal 132
6.3.3 Spectrum 133
6.3.4 Signal power 136
6.3.5 FSK modulation 136
6.4 Phase modulation 139
6.4.1 Principle 139
6.4.2 PSK modulation 141
Chapter 7 Filtering 145
7.1 Definitions and reminders 145
7.1.1 Discrete signals 146
7.1.2 Analog signals 147
7.2 Analog filtering 148
7.2.1 General information 148
7.2.2 Common filters 148
7.2.3 Differential equations and transfer functions 152
7.3 Digital filtering 160
7.3.1 General information 160
7.3.2 Difference equation 161
7.3.3 Transfer function 163
7.3.4 Filter stability 166
7.3.5 Frequency behavior 168
7.3.6 FIR filters 170
7.3.7 IIR filters 173
Chapter 8 The Digital Image 177
8.1 Raster and vector images 177
8.1.1 Raster images 177
8.1.2 Vector images 179
8.2 Notions of colorimetry 179
8.2.1 Grayscale 180
8.2.2 Colors 184
8.2.3 True color and indexed color 188
8.4 Image display modes 190
8.4.1 Matrix coding 190
8.4.2 Vector coding 192
8.4.3 Fractal curves 193
8.5 Compression and compaction 193
8.6 Image formats 195
8.6.1 Raster image formats 195
8.6.2 Vector image formats 196
Chapter 9 2D Computer Graphics 197
9.1 Basic graphics processing 197
9.1.1 Drawing a segment 197
9.1.2 Drawing a circle 201
9.1.3 Windowing 202
9.1.4 Filling and coloring 204
9.2 2D geometric transformations 205
9.2.1 Homogeneous coordinates 205
9.2.2 Translation 206
9.2.3 Rotation around the origin 207
9.2.4 Dilation 208
9.2.5 Symmetries 209
9.2.6 Composition of transformations 210
9.2.7 Object representation 211
9.3 2D parametric curves 212
9.3.1 Using cubic curves 212
9.3.2 Hermite curves 213
9.3.3 Bézier curves 214
9.3.4 B-spline curves 216
Chapter 10 Concepts in Image Processing and Analysis 217
10.1 Image display 218
10.1.1 Simple correspondence 218
10.1.2 Random threshold display 218
10.1.3 Threshold matrix display 220
10.2 Basic image analysis tools 222
10.2.1 Histogram 222
10.2.2 Profiles 224
10.2.3 Level search 224
10.2.4 Information contained in an image 224
10.3 Basic processing 226
10.3.1 Histogram transformation 226
10.3.2 Changing the shape of the histogram: equalization 230
10.3.3 Image subtraction and averaging 233
10.4 Filtering 233
10.4.1 Filtering in the spatial domain 233
10.4.2 Frequency domain filtering 241
10.5 Binary images 245
10.5.1 Morphological operators 246
10.6 Segmentation 247
10.6.1 Outline extraction 248
10.6.2 Regional segmentation 252
Chapter 11 Basics of Image Compression 257
11.1 General information 258
11.1.1 Coding redundancy 258
11.1.2 Interpixel redundancy 259
11.1.3 Psychovisual redundancy 260
11.1.4 Confidence criteria 261
11.1.5 Modeling image compression 262
11.2 Lossless compression or compaction 263
11.2.1 Variable-length coding 263
11.2.2 Bit-plane coding 266
11.2.3 Predictive coding 268
11.3 Lossy compression 269
11.3.1 Predictive coding 269
11.3.2 Transform coding 270
11.4 An image compression standard: JPEG 272
Chapter 12 Elements of Numerical Analysis 277
12.1 Numerical solution of a linear system 278
12.1.1 Exact solution of a linear Cramerian system 278
12.1.2 Principle of iterative methods 280
12.1.3 Diagonal iteration and Gauss-Seidel iteration 282
12.1.4 Direct methods 283
12.2 Numerical solution of fx = 0 287
12.2.1 Introduction 287
12.2.2 General methods 288
12.2.3 Methods applicable to polynomial equations 294
12.3 Numerical integration 297
12.3.1 Introduction 297
12.3.2 Classic methods 297
12.3.3 Polynomial interpolation 302
12.3.4 Quadrature formulas 304
12.3.5 Monte Carlo method 307
12.4 Numerical solution of differential equations 310
12.4.1 Introduction 310
12.4.2 Separate-step algorithms 311
12.4.3 Linked-step methods 318
12.5 Numerical solution of partial differential equations 320
12.5.1 Definitions 320
12.5.2 Finite difference method 321
12.5.3 Resolution examples 325
12.6 Appendices 331
12.6.1 Dichotomy method 331
12.6.2 Iterative method 332
12.6.3 Secant method 332
12.6.4 Tangent method 333
12.6.5 Monte Carlo method Example 12.7 334
12.6.6 Monte Carlo method Example 12.8 336
References 339
List of Authors 343
Index 345
1
Representation of Numbers
CONCEPTS COVERED IN THIS CHAPTER.-
This first part, devoted to the digital representation of information, primarily addresses numbers. Starting with numbers is appropriate because computers were originally designed for calculation purposes.
Since computers operate using only 0s and 1s, it is essential to understand the binary system and the conversions between the decimal and the binary systems, as well as vice versa. In addition, two other systems commonly used in computing, the octal system and the hexadecimal system, are discussed.
The approach to the machine representation of numbers involves working within a fixed range, as computers cannot recognize infinity. This necessitates methods for representing negative numbers and rational numbers. The common solutions used for these cases are described.
References: [STA 07, VEL 19, LIP 83].
Using a computer assumes that the information transmitted to it is in a format or language understandable by its components. Transforming data from a human-readable format into a format understandable by the computing machine is called "information coding".
Modern computers work exclusively with the binary system, which uses a reduced alphabet of {0, 1}. This raises the question of how to represent of common types of information (such as numbers, texts, images, sounds and videos), in binary. The ellipsis suggests that in the future, it might also be possible to represent other sensory experiences, such as smells and tastes, in binary form.
The study will begin with the coding of numbers, as computers were originally designed for computation. The following chapter will then cover the coding of other types of information, including texts, images, sounds and videos.
1.1. Representation of numbers
The decimal system is commonly used for manipulating numbers today, but historically, some civilizations used sexagesimal numbering systems. This approach is still evident in the measurement of time and angles: 1 hour = 60 minutes; 1 minute = 60 seconds, and angles are measured such that 1 flat angle = 180° = 3×60°.
Roman numerals were not very suitable for calculation, serving primarily for counting. The decimal system, which is quite ancient (originating in Egypt in the 3rd millennium BCE and later refined with the invention of 0), is based on the 10 symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and uses positional numbering. As a result, the number 1234 is distinct from the number 3124, despite using the same digits, because the position of each digit is important for determining the number's value.
1.1.1. Position numbering
EXAMPLE 1.1.-
Consider the number 1234. This number can be understood as follows: 1×1,000 + 2×100 + 3×10 + 4, or 1234 = 1×103 + 2×102 + 3×101 + 4×100.
In the decimal system, which as a base of 10 (with 10 digits), the position of each digit in a number corresponds to a power of 10.
In the binary system, which uses only the digits 0 and 1 and has a base of 2, a decimal number like 1234 is written as: 10011010010. This binary representation is understood as follows:
10011010010 = 1×210 + 0×29 + 0×28 + 1×27 + 1×26 + 0×25 + 1×24 + 0×23 + 0×22 + 1×21 + 0×20.
Just like in the decimal system, the position numbering is used in the binary system. In the binary system, the base is 2, and the digits are 0 and 1, which are referred to as bits in computing. The binary can be verified to correspond to the number 1234 (from Example 1.1) by using powers of 2 (see Figure 1.1).
It should be noted that 210 = 1,024 is referred to as a kilobyte (KB) in computing, commonly abbreviated as "K". In this context, 1,024 bytes are equivalent to 1 KB.
Figure 1.1. Powers of 2
Unlike human thinking, computers cannot process infinite numbers and are limited in the range of numbers they can manipulate. To represent an n-bit number, the largest integer that can be represented is 2n - 1. To represent the largest integer with m decimal digits in the binary system, which is 10m - 1, how many n bits are needed to represent this number in a computer?
To represent the largest integer with m decimal digits, the 10m - 1 = 2n - 1 must be satisfied (assuming this is possible). Taking logarithms gives:
m × log10(10) = n × log10(2).
Since log10(10) = 1, this simplifies to
m = n × log10(2)
Solving for n:
It therefore takes approximately (3.32 × m) bits to represent an integer of m decimal digits in the binary system.
1.1.2. The binary system
As noted previously, the binary system is based on two symbols (bits): 0 and 1. Unlike the decimal system, operations in binary are extremely simple. Some may recall learning decimal multiplication tables in elementary school!
This is because, in the binary system, basic operations such as addition and multiplication are much more direct and less complex compared to the decimal system. Binary addition is performed bit by bit (see column 1 of Figure 1.2), where 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 (without carry) and 1 + 1 = 10 (with carry). Binary multiplication follows simple rules (see column 2 of Figure 1.2), where 0 × 0 = 0, 0 × 1 = 0, 1 × 0 = 0 and 1 × 1 = 1.
Figure 1.2. Addition and multiplication in binary
This simplicity in binary operations is one of the reasons why computers use this system for internal calculations. This allows for efficient data manipulation and rapid calculations at the electronic circuit level.
The primary problem to solve is converting between decimal and binary systems. To convert a decimal number into a binary number, a straightforward method based on powers of 2 is used.
Consider the example of covering the decimal number 1234 to binary. Start by finding the largest power of 2 less than or equal to 1234, which is 1,024 = 210. Subtract 1,024 from 1234 to get 210. Next, find the largest power of 2 closest to 210, which is 128 = 27. Subtract 128 from 210 to get 82. Continue this process by finding the closest power of 2 to each resulting value and performing the corresponding subtractions. The sequence of operations is shown in Figure 1.3.
Figure 1.3. Decimal-to-binary conversion
The powers of 2 present in this decomposition are 21, 24, 26, 27 and 210 and the missing powers of 2 are 20, 22, 23, 25, 28 and 29. To write the binary number, use the position numbering rule: place a 1 for each present power of 2 and a 0 for each absent power of 2. Thus, the binary representation is:
When necessary, the subscript 2 indicates a number in the binary system, and the subscript 10 indicates a number in the decimal system.
Now let us move on to the reverse problem: converting a binary number into a decimal number. It is actually simpler because you just write it down with the position numbering rule and do the math. Therefore, to convert this binary number to decimal, each bit of the binary number is multiplied by 2 raised to the power of its position, starting from zero at the far right.
Now, consider how to represent a rational number in base 2. Take the example of the decimal number (14.80078125)10. To express this in base 2 follow this rule for a binary number of the form (0. xyzt . )2 where x, y, z, t, . are bits:
This method can be used to convert a decimal number with fractions into base 2. Applying this method will illustrate the conversion process for the example provided.
EXAMPLE 1.2.-
Consider the decimal number 14.80078125 in base 10. First, convert the integer part (14)10 into binary, which is (1110)2. For the decimal part (0.80078125)10, perform successive multiplications by 2,while recording the integer part of the result at each step:
The decimal part can be expressed as a sum of fractions:
This corresponds to the binary representation (0.11001101)2.
Combining this with the integer part (14)10 = (1110)2, the full binary representation of (14.80078125)10 is:
The calculation performed in the previous example will be useful later. By converting the decimal number (14.80078125)10 to binary, the complete binary representation is (1110.11001101)2. This conversion illustrates the general method for converting decimal numbers to binary numbers using the position numbering rule. This method will be explored in more detail later.
1.1.3. Octal system and hexadecimal system
In the octal system , the base is 8, so there are eight digits available: 0, 1, 2, 3, 4, 5, 6 and 7. Converting a decimal number to octal follows the same principle as converting to binary. Using powers of 8, the number (1234)10 can be represented in octal base. Given that
Break down (1234)10 as follows:
Converting to octal:
The conversion process involves starting with the binary representation of the number, grouping the into packets of 3 from the right, and then using the table in Figure 1.4 to convert each group to octal. For example:
Group the binary...
