Information theory

The theory of information, also known as the mathematical theory of communication (English: mathematical theory of communication) or mathematical theory of information, is a theoretical proposal presented by Claude E. Shannon and Warren Weaver at the end of the 1940s. This theory is related to the mathematical laws that govern the transmission and processing of information. information and is concerned with the measurement of information and the representation of information, as well as the ability of communication systems to transmit and process information. Information theory is a branch of probability theory that studies information and everything related to it: channels, data compression and cryptography, among others.

History

Information theory emerged at the end of World War II, in the 1940s. It was indicated by Claude E. Shannon through an article published in the Bell System Technical Journal in 1948, entitled A Mathematical Theory of Communication (full text in English). At this time, the aim was to use communication channels more efficiently, sending a quantity of information through a certain channel and measuring its capacity; the optimal transmission of messages was sought. This theory is the result of work started in the 1910s by Andrei A. Markovi, who was followed by Ralph Hartley in 1927, who was the forerunner of binary language. In turn, Alan Turing in 1936, made the scheme of a machine capable of processing information with the emission of symbols, and finally Claude Elwood Shannon, American mathematician, electronic engineer and cryptographer, known as "the father of the theory of information”, together with Warren Weaver, contributed to the culmination and establishment of the Mathematical Theory of Communication of 1949 –which today is known worldwide by all as the Information Theory-. Weaver managed to give it a greater scope than the initial approach, creating a simple and linear model: Source/encoder/message channel/decoder/destination. The need for a theoretical basis for communication technology arose from the increasing complexity and widespread use of communication channels, such as the telephone, teletype networks, and radio communication systems. Information theory also encompasses all other forms of information transmission and storage, including television and the electrical impulses that are transmitted in computers and in the optical recording of data and images. The idea is to ensure that the bulk transport of data is not in any way a loss in quality, even if the data is compressed in some way. Ideally, the data can be restored to its original form upon arrival at its destination. In some cases, however, the goal is to allow data to be converted in some form for mass transmission, received at the destination point, and easily converted back to its original format, without losing any of the transmitted information.

Theory development

The model proposed by Shannon is a general communication system that starts from an information source that emits a message. Through a transmitter, a signal is emitted that travels through a channel, where it can be interfered by some noise. The signal leaves the channel, reaches a receiver that decodes the information, later converting it into a message that is passed on to a recipient. With the model of information theory, the aim is to determine the cheapest, fastest and safest way to encode a message, without the presence of any noise complicating its transmission. For this, the recipient must understand the signal correctly; The problem is that even if there is the same code involved, this does not mean that the recipient will capture the meaning that the sender wanted to give to the message. Encryption can refer to both the transformation of voice or image into electrical or electromagnetic signals, or the encryption of messages to ensure your privacy. A fundamental concept in information theory is that the amount of information contained in a message is a well-defined and measurable mathematical value. The term amount does not refer to the amount of data, but to the probability that a message, within a set of possible messages, will be received. Regarding the amount of information, the highest value is assigned to the message that is least likely to be received. If it is known with certainty that a message is going to be received, its amount of information is zero.

Purpose

Another important aspect within this theory is the resistance to distortion caused by noise, the ease of encoding and decoding, as well as the transmission speed. This is why it is said that the message has many meanings, and the addressee extracts the meaning that must be attributed to the message, as long as there is the same code in common. Information theory has certain limitations, such as the meaning of the concept of code. The meaning to be conveyed does not count as much as the number of alternatives necessary to define the fact without ambiguity. If the selection of the message arises solely between two different alternatives, Shannon's theory arbitrarily postulates that the value of the information is one. This unit of information is called a bit. For the information value to be a bit, all alternatives must be equally likely and available. It is important to know if the information source has the same degree of freedom to choose any possibility or if it is under some influence that leads to a certain choice. The amount of information grows when all alternatives are equally likely or the greater the number of alternatives. But in real communicative practice, not all alternatives are equally likely, which constitutes a type of stochastic process called Markov. The Markov subtype says that the string of symbols is configured such that any sequence in that string is representative of the entire string.

Theory applied to technology

Information Theory is still today in relation to one of the technologies in vogue, the Internet. From a societal point of view, the Internet represents significant potential benefits, as it offers unprecedented opportunities to empower individuals and connect them with increasingly rich sources of digital information. The Internet was created from a project of the United States Department of Defense called ARPANET (Advanced Research Projects Agency Network) started in 1969 and whose main purpose was the research and development of communication protocols for networks. wide area to link packet transmission networks of different types capable of withstanding the most difficult operating conditions, and continue to function even with the loss of a part of the network (for example in case of war). These investigations resulted in the TCP/IP (Transmission Control Protocol/Internet Protocol) protocol, a very solid and robust communications system under which all the networks that make up what is currently known as Internet. The enormous growth of the Internet is due in part to the fact that it is a network based on government funds from each country that is part of the Internet, which provides a practically free service. At the beginning of 1994 an explosive growth of companies with commercial purposes began to occur on the Internet, thus giving rise to a new stage in the development of the network. Broadly described, TCP/IP puts the information to be sent into packets and takes it out of the packets for use when it is received. These packages can be compared to mailing envelopes; TCP/IP saves the information, closes the envelope and on the outside puts the address to which it is addressed and the address of the sender. Through this system, packets travel through the network until they reach the desired destination; once there, the destination computer removes the envelope and processes the information; if necessary, it sends a response to the originating computer using the same procedure. Every machine that is connected to the Internet has a unique address; this means that the information that is sent does not mistake the destination. There are two ways to give addresses, with letters or with numbers. Computers actually use numerical addresses to send packets of information, but letter addresses were implemented to make it easier for humans to handle. A numeric address is made up of four parts. Each of these parts is divided by points.

Example: sedet.com.mx 107.248.185.1

One of the applications of information theory is ZIP files, documents that are compressed for transmission via email or as part of data storage procedures. The compression of the data makes it possible to complete the transmission in less time. At the receiving end, software is used to unzip or unzip the file, restoring the documents contained in the ZIP file to their original format. Information theory also comes into use with other file types; for example, audio and video files played on an MP3/MP4 player are compressed for easy download and storage on the device. When the files are accessed they are unzipped so they are immediately available for use.

Elements of theory

Scheme of communication devised by Claude E. Shannon.

Source

A source is anything that emits messages. For example, a source can be a computer and messages its files; a source can be a data transmission device and messages the data sent, etc. A source is itself a finite set of messages: all the possible messages that the source can emit. In data compression, the file to be compressed will be taken as the source and the characters that make up said file will be taken as messages.

Font Types

Due to the generative nature of its messages, a font can be either random or deterministic. Due to the relationship between the messages emitted, a source can be structured or unstructured (or chaotic).

There are several types of fonts. For information theory, random and structured sources are of interest. A source is random when it is not possible to predict what is the next message to be emitted by it. A source is structured when it has a certain level of redundancy; an unstructured or pure information source is one in which all messages are absolutely random without any relationship or apparent meaning. This type of font emits messages that cannot be compressed; a message, in order to be compressed, must have a certain degree of redundancy; raw information cannot be compressed without loss of knowledge about the message.

Message

A message is a set of 0's and 1's. A file, a packet of data traveling over a network, and anything that has a binary representation can be considered a message. The concept of message also applies to alphabets of more than two symbols, but since we are dealing with digital information we will almost always refer to binary messages.

Code

A code is a set of ones and zeros that are used to represent a certain message according to pre-established rules or conventions. For example, we can represent message 0010 with the code 1101 used to encode the (NOT) function. The way in which we encode is arbitrary. A message may, in some cases, be represented with a code that is shorter than the original message. Suppose that any message S is encoded using a certain algorithm such that each S is encoded in L(S) bits; we then define the information contained in the message S as the minimum amount of bits needed to encode a message.

Information

The information contained in a message is proportional to the number of bits that are required as a minimum to represent the message. The concept of information can be more easily understood if we consider an example. Suppose we are reading a message and we have read "c string"; the probability that the message will continue with "characters" she's very tall. Thus, when we actually receive "characters" The amount of information that reached us is very low because we were in a position to predict what was going to happen. The occurrence of messages with a high probability of occurrence provides less information than the occurrence of less likely messages. If after "c string" we read "himichurri" the amount of information we are receiving is much greater.

Entropy and information

The information is treated as a physical magnitude, characterizing the information of a sequence of symbols using entropy. It is part of the idea that channels are not ideal, although nonlinearities are often idealized, to study various methods of sending information or the amount of useful information that can be sent through a channel.

The information necessary to specify a physical system has to do with its entropy. In particular, in certain areas of physics, extracting information from the current state of a system requires reducing its entropy, so that the entropy of the system (S{displaystyle S}) and the amount of information (I{displaystyle I}) removable are related by:

S≥ ≥ S− − I≥ ≥ 0{displaystyle Sgeq S-Igeq 0}

Entropy of a source

According to information theory, the information level of a source can be measured by the entropy of the source. Studies on entropy are of paramount importance in information theory and are mainly due to C. E. Shannon. There is, in turn, a large number of properties regarding the entropy of random variables due to A. Kolmogorov. Given a source F that emits messages, it is common to observe that the messages emitted are not equiprobable but rather have a certain probability of occurrence depending on the message. To encode the messages from a source, we will try to use fewer bits for the most probable messages and a greater number of bits for the less probable messages, in such a way that the average number of bits used to encode the messages is less than the number of bits average of the original messages. This is the basis of data compression. This type of source is called a 0-order source, since the probability of occurrence of a message does not depend on previous messages. Higher order sources can be represented by a 0-order source using appropriate modeling techniques. We define the probability of occurrence of a message in a source as the number of occurrences of said message divided by the total number of messages. Suppose that P_i is the probability of occurrence of message-i from a source, and suppose that L_i is the length of the code used to represent said message. The average length of all encoded messages from the source can be obtained as:

H=␡ ␡ i=0nPiLi{displaystyle H=sum _{i=0}{n}P_{i}

• Weighted average of code lengths according to their probability of occurrence, to number H it is called "Entropy of the source" and has great importance. The entropy of the source determines the level of compression that we can obtain for a set of data. If we consider as a source a file and get the chances of occurrence of each character in the file we can calculate the average length of the compressed file. It is shown that it is not possible to statistically compress a message/archive beyond its entropy, which implies that considering only the frequency of appearance of each character the entropy of the source gives us the theoretical limit of compression. Through other non-state techniques, this limit may be overcome.
• The goal of data compression is to find the L_i minimizing H; also the L_i to be determined on the basis of P_i, because the length of the codes must depend on the probability of occurrence of the same (the most likely we want to encode them in less bits). It is thus proposed:

H=␡ ␡ i=0nPif(Pi){displaystyle H=sum _{i=0}^{n}P_{i}f(P_{i}}}}}

From here and after intricate mathematical procedures that were opportunely demonstrated by Shannon, it is arrived at that H is minimum when f(P_i) = log ₂ (1/P_i). Then:

H=␡ ␡ i=0nPi(− − log2 Pi){displaystyle H=sum _{i=0}{n}P_{i}(-log _{2}P_{i})}}

The minimum length with which a message can be encoded can be calculated as L_i=log₂(1/P_i) = -log₂(P_i). This gives an idea of the length to use in the codes to use for the characters of a file based on their probability of occurrence. Replacing L_i we can write H as:

H=␡ ␡ i=0n− − Pilog2 Pi{displaystyle H=sum _{i=0}^{n}-P_{i}log _{2}P_{i}}

From this it follows that the entropy of the source depends solely on the probability of occurrence of each message from it; hence the importance of statistical compressors (those that are based on the probability of occurrence of each character). Shannon demonstrated, in due course, that it is not possible to compress a source statistically beyond the level indicated by its entropy.

Other aspects of the theory

• Sources of information
  • Entropy
  • Mutual information
  • Neguentropy
  • Nyquist-Shannon sampling theorem

• Channels
  • Capacity

• Data compression
  • Codification of source
  • Non-singular codes
  • Uniquely decoding codes
    • Extension of code
  • Prefix codes (or instant codes)

• Error control
  • ARQ
  • FEC
    • Stop and wait
    • Multiple reject
    • Selective reject
  • Hybrid techniques
    • Code concatenation
    • Type 1
    • Type 2

• Detection of errors
  • Bits of redundancy
    • Error control methods
      • Parity
        • Codes and self-correctors
          • Block codes
            • Distance Hamming
          • Horizontal and vertical parity
      • Linear codes
        • Cyclical codes
          • CRC16
          • CRC32