Linear code | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as a hybrid of these two types. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding). Linear codes are used in forward error correction and are applied in methods for transmitting symbols (e.g., bits) on a communications channel so that, if errors occur in the communication, some errors can be corrected or detected by the recipient of a message block. The codewords in a linear block code are blocks of symbols that are encoded using more symbols than the original value to be sent. A linear code of length n transmits blocks containing n symbols. For example, the [7,4,3] Hamming code is a linear binary code which represents 4-bit messages using 7-bit codewords. Two distinct codewords d

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (41)

Related publications

Related people (12)

Related people

Related units (4)

Related units

Related concepts (12)

Related concepts

Related courses (4)

Related courses

Related lectures (5)

Related lectures

Error correction code

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliabl

Reed–Solomon error correction

Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, the most prominent of which include consumer t

Block code

In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide rang

EE-543: Advanced wireless receivers

Students extend their knowledge on wireless communication systems to spread-spectrum communication and to multi-antenna systems. They also learn about the basic information theoretic concepts, about channel coding, and bit-interleaved coded modulation.

COM-102: Advanced information, computation, communication II

Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?

EE-584: Spacecraft design and system engineering

The main objective of the course is to introduce the concept of space system design and engineering. The course will describe the various subsystems involved in the design of a satellite. It will also describe the techniques of systems engineering that are used to obtain a coherent satellite design.

New Results On The Pseudoredundancy

Zihui Liu

The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding minimum pseudoweight equals its minimum Hamming distance. By using the value assignment of Chen and Klove we present new results on the pseudocode-word redundancy of binary linear codes. In particular, we give several upper bounds on the pseudoredundancies of certain codes with repeated and added coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.

2019

Towards an Algebraic Network Information Theory: Distributed Lossy Computation of Linear Functions

Chen Feng, Michael Christoph Gastpar, Sung Hoon Lim, Adriano Pastore

Consider the important special case of the K-user distributed source coding problem where the decoder only wishes to recover one or more linear combinations of the sources. The work of Körner and Marton demonstrated that, in some cases, the optimal rate region is attained by random linear codes, and strictly improves upon the best-known achievable rate region established via random i.i.d. codes. Recent efforts have sought to develop a framework for characterizing the achievable rate region for nested linear codes via joint typicality encoding and decoding. Here, we make further progress along this direction by proposing an achievable rate region for simultaneous joint typicality decoding of nested linear codes. Our approach generalizes the results of Körner and Marton to computing an arbitrary number of linear combinations and to the lossy computation setting.

2019

Towards an algebraic network information theory: Simultaneous joint typicality decoding

Chen Feng, Michael Christoph Gastpar, Sung Hoon Lim, Adriano Pastore

Recent work has employed joint typicality encoding and decoding of nested linear code ensembles to generalize the compute-forward strategy to discrete memoryless multiple-access channels (MACs). An appealing feature of these nested linear code ensembles is that the coding strategies and error probability bounds are conceptually similar to classical techniques for random i.i.d. code ensembles. In this paper, we consider the problem of recovering K linearly independent combinations over a K-user MAC, i.e., recovering the messages in their entirety via nested linear codes. While the MAC rate region is well-understood for random i.i.d. code ensembles, new techniques are needed to handle the statistical dependencies between competing codeword K-tuples that occur in nested linear code ensembles.

2017