Cyclic Redundancy Code - CRC

Cyclic Redundancy Code (CRC) is commonly used to determine the correctness of a data transmission or storage.

The fundamental mathematics behind the CRC is polynomial division. An arbitrary message (a fixed block of k information bits) is treated as if each bit were the binary coefficient of a polynomial of degree k-1. Let’s assume that we augment that message by simply adding some arbitrary number of bits to the end of the message which we will call the parity bits. If the original message is augmented such that the new message (original message + parity bits), which we will refer to as the code word, is evenly divisible by a known polynomial, which we will call the generator polynomial, then the receiver can assume that there were no transmission errors. However, in practice, it is possible to introduce errors into the received message that make detection of these errors impossible for a given generator polynomial. Many of today’s communications protocols, such as HDLC and Ethernet, use 16-bit and 32-bit CRCs, respectively. The native implementation for computing and checking a CRC is bit-based which typically makes hardware a more natural fit.

CRC Theory

Let's assume that we augment our message polynomial m(x) of degree k by multiplying it by an arbitrary polynomial g(x). We will refer to g(x) as the generator polynomial.

• c(x) = m(x)g(x)

We have now increased the size of the message by the degree of the generator polynomial. This augmented message c(x) is referred to as the code word and is of degree n. It is obvious that we can recover the original message m(x) by dividing c(x) by g(x).

We can also write the code word as the sum of two polynomials, the original message m(x) where each component is increased in degree by (n-k) and an arbitrary polynomial r(x) of degree (n-k). This form has the advantage of not disturbing the original message and is the basis for the CRC algorithm.

• c(x) = m(x)x^(n–k) + r(x)

We will refer to r(x) as the remainder polynomial, which is the remainder of m(x)x^n–k divided by g(x).

The binary coefficients of the remainder polynomial are the parity bits which get appended to the end of the original message. So what we wind up with is a code word that is simply the original message followed by a tail of parity bits. The example below shows the resulting code word derived from the input ASCII hex values for the test sequence 123456789 and the computed CRC given the CRC-16 generator polynomial.

IP Address

Class A

The largest grouping of addresses is the class A group. Class A network addresses can be identified by a unique bit pattern in the 32bit address.

Representation : 0nnnnnnn 11111111 11111111 11111111

The first eight bits of a class A address indicate the network number. The remaining 24 bits can be modified by the administrative user of the network address to represent addresses found on their “local” devices. In the representation the “n's" indicate the location of the network number bits in the address. The “l's" represent the locally administered portion of the address. As you can see, the first bit of a class A network address is always a zero.

With the first bit of class A address always zero, the class A network numbers begin at 1 and end at 127. With a 24-bit locally administered address space, the total number of addresses in a class A network is 224 or 16,777,216. Each network administrator who receives a class A network can support 16 million hosts. But remember, there are only 127 possible class A addresses in the design, so only 127 large networks are possible.

Here is a list of class A network numbers:

• 10.0.0.0
• 44.0.0.0
• 101.0.0.0
• 127.0.0.0

Notice that these network numbers range between 1.0.0.0 and 127.0.0.0, the minimum and maximum numbers.

Range : 1.0.0.0 - 127.0.0.0
Total Networks : 127
Total Addresses : 16,777,216

Class B

The next grouping of addresses is the class B group. Class B network addresses can be identified by a unique bit pattern in the 32-bit address.

10nnnnnn nnnnnnnn 11111111 11111111

The first 16 bits of a class B address indicate the network number. The remaining 16 bits can be modified by the administrative user of the network address to represent addresses found on their “local” hosts. A class B address is identified by the 10 in the first two bits.

With the first two bits of class B address containing 10, the class B network numbers begin at 128 and end at 191. The second dotted decimal in a class B address is also part of the network number. A 16-bit locally administered address space allows each class B network to contain 216 or 65,536 addresses. The number of class B networks available for administration is 16,384.
Here is a list of class B network numbers:

• 137.55.0.0
• 129.33.0.0
• 190.254.0.0
• 150.0.0.0
• 168.30.0.0

Notice that these network numbers range between 128.0.0.0 and 191.255.0.0, the minimum and maximum numbers, respectively. And remember that the first two dotted decimal numbers are included in the network number since the network number in a class B address is 16 bits long.


Range : 128.0.0.0 - 191.255.0.0
Total Networks : 16,384
Total Addresses : 65,536

Class C

The next grouping of addresses is the class C group. Class C network addresses can be identified by a unique bit pattern in the 32bit address.

110nnnnn nnnnnnnn nnnnnnnn 11111111


The first 24 bits of a class C address indicate the network number. The remaining 8 bits can be modified by the administrative user of the network address to represent addresses found on their “local” hosts. A class C address is identified by the 110 in the first three bits.

With the first three bits of class C address containing 110, the class C network numbers begin at 192 and end at 223. The second and third dotted decimals in a class C address are also part of the network number. An 8-bit locally administered address space allows each class C network to contain 28 or 256 addresses. The number of class C networks available for administration is 2,097,152.

Here is a list of class C network numbers:

• 204.238.7.0
• 192.153.186.0
• 199.0.44.0
• 191.0.0.0
• 222.222.31.0

Notice that these network numbers range between 192.0.0.0 and 223.255.255.0, the minimum and maximum numbers, respectively. And remember that the first three dotted decimal numbers are included in the network number since the network number in a class C address is 24 bits long.

Range : 192.0.0.0 - 223.255.255.0
Total Networks : 2,097,152
Total Addresses : 256

3G Architectures

When third-generation (3G) systems were initially considered, the goal was to enable a single global communication standard that could fulfill the needs of anywhere and anytime communication. International Telecommunications Union’s (ITU) International Mobile Telecommunications (IMT-2000) vision (ITU-T 2000a) called for a common spectrum worldwide (1.8–2.2 GHz band), support for multiple radio environments (including cellular, satellite, cordless, and local area networks), a wide range of telecommunications services (voice, data, multimedia, and the Internet), flexible radio bearers for increased spectrum efficiency, data rates up to 2 Mbps in the initial phase, and maximum use of Intelligent Network (IN) capabilities for service development and provisioning. ITU envisioned global seamless roaming and service delivery across IMT-2000 family networks, with enhanced security and performance as well as integration of satellite and terrestrial systems to provide global coverage. Although some of the technical goals have been achieved, the dream of universal and seamless communication remains elusive. As a reflection of the regional, political, and commercial realities of the mobile communications business, the horizon of third-generation mobile communications is dominated by two largely incompatible systems.

One realization of IMT-2000 vision is called the Universal Mobile Telecommunications System (UMTS), developed under 3GPP. This system has evolved from the second generation Global System for Mobile Communications (GSM) and has gained significant support in Europe, Japan, and some parts of Asia. The system is sometimes simply referred to as the 3GPP system.

The second version of the IMT-2000 vision continues to be standardized under 3GPP2 and is referred to as the CDMA2000 or 3GPP2 system. This system has evolved from the second-generation IS-95 system and has been deployed in the United States, South Korea, Belarus, Romania, and some parts of Russia, Japan, and China, that is, mostly the regions that had IS-95 presence.

These two systems are similar in functional terms, particularly from a user’s point of view. However, they use significantly different radio access technologies and differ significantly in some of their architectural details, making them largely incompatible.

The Evolution of Mobile Networks

To date, there have been three distinct generations of mobile cellular networks. The first three generations of mobile networks are conventionally defined by air interfaces and transport technologies. However, it is worth noting that each generation clearly provided an increase in functionality to the mobile user, and could therefore be defined in those terms, rather than in transport technology terms.

• 1G: Basic mobile telephony service
• 2G: Mobile telephony service for mass users with improved ciphering and efficient utilization
• of the radio spectrum
• 2.5G: Mobile Internet services
• 3G: Enhanced 2.5G services plus global roaming, and emerging new applications

The first generation (1G) is based on analog cellular technology, such as the American Mobile Phone Service (AMPS) in the United States and the NTT system in Japan. The second-generation (2G) technology is based on digital cellular technology. Commercially deployed examples of the second generation are the Global System for Mobile Communications (GSM), the North American Version of the CDMA Standard (IS-95) and in Japan, the Personal Digital Cellular (PDC). GSM also provides interregional roaming functionality. Owing to this functionality, GSM continues to show outstanding progress by obtaining 1 billion customers worldwide in 2004.

Packet-switched networks were overlaid onto many of the 2G networks, in the middle of the 2G period. Generally, 2G networks with packet-switched communication systems added are referred to as 2.5G mobile networks.

2.5G mobile networks facilitate instant connections where information can be sent or received almost immediately and without any user activity required to establish a connection. This is why 2.5G mobile devices are commonly referred to be as being always connected or always on.

Universal Mobile Telecommunications System (UMTS)

The Universal Mobile Telecommunications System (UMTS) is a third-generation wireless telecommunication system and follows in the footsteps of GSM and GPRS. Since GSM was standardized in the 1980s, huge progress has been made in many areas of telecommunication. This allowed system designers at the end of the 1990s to design a new system that goes far beyond the capabilities of GSM and GPRS. UMTS combines the properties of the circuit-switched voice network with the properties of the packet-switched data network and offers a multitude of new possibilities compared to the earlier systems. UMTS was not defined from scratch and reuses a lot of GSM and GPRS.


When 3G standardization efforts began in the latter half of the 1990s, a conscious effort was made to align 3G with the existing 2G GSM solutions and technologies. GSM at that time was, and for the most part still is, the dominant mobile communications standard through much of Europe and Asia. The decision to base 3G specifications on GSM was motivated by widespread deployment of networks based on GSM standards, the need to preserve some backward compatibility, and the desire to utilize the large investments made in the GSM networks. As a result, despite its many added capabilities, the UMTS core network bears significant resemblance to the GSM network.

Enhanced Data Rates for GSM Evolution (EDGE) – EGPRS

In order to further increase the data transmission speeds a new modulation and coding scheme,which uses 8PSK, has been introduced into the standards. The new coding scheme forms thebasis of the ‘enhanced data rates for GSM evolution’ package, which is also called EDGE.

The packet-switched part of EDGE is also referred to in the standard as enhanced GPRS or EGPRS. In the GPRS context, EGPRS and EDGE are often used interchangeably. By using 8PSK, EDGE puts three bits into a single transmission step. This way, data transmission speeds can be up to three times faster compared to GSM and GPRS which both use GMSK modulation which only transmits a single bit per transmission step. While with GMSK the two possibilities 0 and 1 are coded as two positions in the I/Q space, 8PSK codes the three bits in eight different positions in the I/Q space.

General Packet Radio Service(GPRS)

In the mid-1980s voice calls were the most important service for fixed and wireless networks. This is the reason why GSM was initially designed and optimized for voice transmission. Since the mid-1990s, however, the importance of the Internet has been constantly increasing. GPRS, the General Packet Radio Service, enhances the GSM standard to transport data in an efficient manner and thus allows wireless devices to access the Internet.

Circuit Switched Data Transmission over GSM

The GSM network was initially designed as a circuit-switched network. All resources for a voice or data session are set up at the beginning of the call and are reserved for the user until the end of the call. The dedicated resources assure a constant bandwidth and end-to-end delay time. This has a number of advantages for the subscriber:

• Data that is sent does not need to contain any signaling information such as information about the destination. Every bit simply passes through the established channel to the receiver. Once the connection is established no overhead, e.g. addressing information, is necessary to send and receive the information.
• As the circuit-switched channel has a constant bandwidth the sender does not have to worry about a permanent or temporary bottleneck in the communication path. This is especially important for a voice call. As the data rate is constant, any bottleneck in the communication path would lead to a disruption of the voice call.
• Furthermore, circuit-switched connections have a constant delay time. This is the time between sending a bit and receiving it at the other end. The greater the distance between the sender and receiver the longer the delay time. This makes a circuit-switched connection ideal for voice applications as they are extremely sensitive to a variable delay time. If a constant delay time cannot be guaranteed, a buffer at the receiving end is necessary. This adds additional unwanted delay especially for applications like voice calls.

While circuit-switched data transmission is ideally suited for voice transmissions, there are a number of grave disadvantages for data transmission with variable bandwidth usage. Web browsing is a typical application with variable or ‘bursty’ bandwidth usage. For sending a request to a web server and receiving the web page, as much bandwidth as possible is desired to receive the web page as quickly as possible. As the bandwidth of a circuit switched channel is constant there is no possibility of increasing the data transmission speed while the page is being downloaded. After the page has been received no data is exchanged while the subscriber reads page. The bandwidth requirement during this time is zero. The resources are simply unused during this time and are thus wasted.

Packet Switched Data Transmission over GPRS

For bursty data applications it would be far better to request resources to send and receive data and release them again after the transmission. This can be done by collecting the data in packets before it is sent over the network. This method of sending data is called ‘packet switching’. As there is no longer a logical end-to-end connection, every packet has to contain a header. The header for example contains information about the sender (source address) and the receiver (destination address) of the packet. This information is used in the network to route the packets through the different network elements. In the Internet for example the source and destination addresses are the IP addresses of the sender and receiver.

To be able to send packet-switched data over existing GSM networks, the General Packet Radio Service (GPRS) was conceived as a packet-switched addition to the circuit-switched GSM network. It should be noted that IP packets can be sent over a circuit-switched GSM data connection as well. However, until they reach the Internet service provider they are transmitted in a circuit-switched channel. GPRS on the other hand is an end-to-end packet switched network and IP packets are sent packet switched from end to end.


The packet-switched nature of GPRS also offers a number of other advantages for bursty applications over GSM circuit-switched data transmission:

• GPRS is usually charged by volume and not by time. For subscribers this has the advantage that they pay for downloading a web page but not for the time reading it, as would be the case with a circuit-switched connection. For the operator of a wireless network it has the advantage that the scarce resources on the air interface are not wasted by ‘idle’ data calls because they can be used for other subscribers.
• GPRS dramatically reduces the call set-up time. Similar to a fixed-line analog modem, a GSM circuit-switched data call takes about 20 seconds to establish a connection with the Internet service provider. GPRS accomplishes the same in less than 5 seconds.
• As the subscriber does not pay for the time when no data is transferred, the call does not have to be disconnected to save costs. This is called ‘always-on’ and enables applications like email programs to poll for incoming emails in certain intervals or allows messaging clients like Yahoo or MSN messenger to wait for incoming messages.
• When the subscriber is moving, by train for example, it happens quite frequently that the mobile has bad network coverage or even loses the network completely for some time. When this happens, circuit-switched connections are disconnected and have to be manually re-established once network coverage is available again.GPRSconnections on the other hand are not dropped as the logical GPRS connection is independent of the physical connection to the network. After regaining coverage the interrupted data transfer simply resumes.

The SIM Card - Subscriber Identity Module

Despite its small size, the SIM card is one of the most important parts of a GSM network because it contains all the subscription information of a subscriber. Since it is standardized, a subscriber can use any GSM or UMTS phone by simply inserting the SIM card. Exceptions are phones that contain a ‘SIM lock’ and thus only work with a single SIM card or only with the SIM card of a certain operator. However, this is not a GSM restriction. It was introduced by mobile phone operators to ensure that a subsidized phone is only used with SIM cards of their network.

The most important parameters on the SIM card are the IMSI and the secret key (Ki), which is used for authentication and the generation of ciphering keys (Kc). With a number of tools, which are generally available on the Internet free of charge, it is possible to read out most parameters from the SIM card, except for sensitive parameters that are read protected. Protected parameters can only be accessed with a special unlock code that is not available to the end user.

Astonishingly, a SIM card is much more than just a simple memory card as it contains a complete microcontroller system that can be used for a number of additional purposes. The mobile phone cannot access the information on the EEPROM directly, but has to request the information from the SIM’s CPU. Therefore, direct access to sensitive information is prohibited.

Furthermore, the microcontroller system on the SIM can also execute programs which the network operator may have installed on the SIM card. This is done via the SIM application toolkit (SAT) interface, which is specified in 3GPP TS. With the SAT interface, programs on the SIM card can access functionalities of the mobile phone such as waiting for user input, or can be used to show text messages and menu entries on the display. Many mobile network operators use this functionality to put an operator-specific menu item into the overall menu structure of the mobile phone’s graphical user interface. In the menu created by the SIM card program, the subscriber can, for example, request a current news overview. When the subscriber enters the menu, all user input via the keypad is forwarded by the mobile phone to the SIM card. The program on the SIM card in this example would react to the news request by generating an SMS, which it then instructs the mobile phone to send to the network. The network replies with one or more SMS messages which contain a news overview. The SIM card can then extract the information from the SMS messages and present the content to the subscriber.

The mobile phone can only access the SIM card if the user has typed in the PIN when the phone is started. The mobile phone then uses the PIN to unlock the SIM card. SIM cards of some network operators, however, allow deactivating the password protection and thus the user does not have to type in a PIN code when the mobile phone is switched on. Despite unlocking the SIM card with the PIN, the mobile phone is still restricted to only being able to read or write certain files. Thus, it is not possible for example to read or write the file which contains the secret key Ki even after unlocking the SIM card with the PIN.

Location area and Location area update

As the network needs to be able to forward an incoming call, the subscriber’s location must be known. After the mobile phone is switched on, its first action is to register with the network. Therefore the network becomes aware of the current location of the user, which can change at any time due to the mobility of the user. If the user roams into the area of a new cell it may need to inform the network of this change. In order to reduce the signaling load in the radio network, several cells are grouped into a location area. The network informs the mobile station via the BCCH of a cell not only of the cell-ID but also of the location area that the new cell belongs to. The mobile station thus only has to report its new location if the new cell belongs to a new location area. Grouping several cells into location areas not only reduces the signaling load in the network but also reduces the power consumption of the mobile. A disadvantage of this method is that the network operator is only aware of the current location area of the subscriber but not of the exact cell. Therefore, the network has to search for the mobile station in all cells of a location area for an incoming call or SMS. This procedure is called paging. The size of a location area can be set by the operator depending on his particular needs. In operational networks, usually 20 to 30 cells are grouped into a location area.

Global System for Mobile Communications - GSM

At the beginning of the 1990s, GSM, the Global System for Mobile Communications triggered an unprecedented change in the way people communicate with each other. While earlier analog wireless systems were used by only a few people, GSM was used by over 1.5 billion subscribers worldwide at the end of 2005. This has mostly been achieved by the steady improvements in all areas of telecommunication technology and due to the steady price reductions for both infrastructure equipment and mobile phones.


Standards

As many telecom companies compete globally for orders of telecommunication network operators, standardization of interfaces and procedures is necessary. Without standards, which are defined by the International Telecommunication Union (ITU), it would not be possible to make phone calls internationally and network operators would be bound to the supplier they initially select for the delivery of their network components. One of the most important ITU standards is the signaling system number 7 (SS-7), which is used for call routing.

GSM, for the first time, set a common standard for Europe for wireless networks, which has also been adopted by many countries outside Europe. This is the main reason why subscribers can roam in GSM networks across the world that have roaming agreements with each other. The common standard also substantially reduces research and development costs as hardware and software can now be sold worldwide with only minor adaptations for the local market. The European Telecommunication Standards Institute (ETSI), which is also responsible for a number of other standards, was the main body responsible for the creation of the GSM standard. The ETSI GSM standards are composed of a substantial number of standards documents each called a technical specification (TS), which describe a particular part of the system.

Transmission Speeds

The smallest transmission speed unit in a telecommunication network is the digital signal level 0 (DS0) channel. It has a fixed transmission speed of 64 kbit/s. Such a channel can be used to transfer voice or data and thus it is usually not called a speech channel but simply referred to as a user data channel. The reference unit of a telecommunication network is an E-1 connection in Europe and a T-1 connection in the United States, which use either a twisted pair or coaxial copper cable. The gross data rate of an E-1 connection is 2.048 Mbit/s and 1.544 Mbit/s for a T-1. An E-1 is divided into 32 timeslots of 64 kbit/s each while a T-1 is divided into 24 timeslots of 64 kbit/s each. One of the timeslots is used for synchronization which means that 31 timeslots for an E-1 or 23 timeslots for a T-1 respectively can be used to transfer data. In practice, only
29 or 30 timeslots are used for user data transmission while the rest (usually one or two) are used for SS-7 signaling data.