|
Reed–Muller Expansion
In Boolean logic, a Reed–Muller expansion (or Davio expansion) is a decomposition of a Boolean function. For a Boolean function f(x_1,\ldots,x_n) : \mathbb^n \to \mathbb we call : \begin f_(x) & = f(x_1,\ldots,x_,1,x_,\ldots,x_n) \\ f_(x)& = f(x_1,\ldots,x_,0,x_,\ldots,x_n) \end the positive and negative cofactors of f with respect to x_i, and : \begin \frac & = f_(x) \oplus f_(x) \end the boolean derivation of f with respect to x_i, where denotes the XOR operator. Then we have for the Reed–Muller or positive Davio expansion: : f = f_ \oplus x_i \frac. Description This equation is written in a way that it resembles a Taylor expansion of f about x_i=0. There is a similar decomposition corresponding to an expansion about x_i=1 (negative Davio expansion): : f = f_ \oplus \overline_i \frac. Repeated application of the Reed–Muller expansion results in an XOR polynomial in x_1,\ldots,x_n: : f = a_1 \oplus a_2 x_1 \oplus a_3 x_2 \oplus a_4 x_1 x_2 \oplus \ldots \op ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boolean Logic
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses Logical connective, logical operators such as Logical conjunction, conjunction (''and'') denoted as ∧, Logical disjunction, disjunction (''or'') denoted as ∨, and the negation (''not'') denoted as ¬. Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction and division. So Boolean algebra is a formal way of describing logical operations, in the same way that elementary algebra describes numerical operations. Boolean algebra was introduced by George Boole in his first book ''The Mathematical Analysis of Logic'' (1847), and set forth more fully in his ''The Laws of Thought, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Karnaugh Map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logical diagram'' aka Marquand diagram but with a focus now set on its utility for switching circuits. Veitch charts are also known as Marquand–Veitch diagrams or, rarely, as Svoboda charts, and Karnaugh maps as Karnaugh–Veitch maps (KV maps). The Karnaugh map reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability. It also permits the rapid identification and elimination of potential race conditions. The required Boolean results are transferred from a truth table onto a two-dimensional grid where, in Karnaugh maps, the cells are ordered in Gray code, and each cell position represents one combination of input conditions. Cells are also known as minterms, while each cell value represents the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
EETimes
''EE Times'' (''Electronic Engineering Times'') is an electronics industry magazine published in the United States since 1972. EE Times is currently owned by AspenCore, a division of Arrow Electronics since August 2016. Since its acquisition by AspenCore, EE Times has seen major editorial and publishing technology investment and a renewed emphasis on investigative coverage. New features include The Dispatch, which profiles frontline engineers and unpacks the real-life design problems and their solutions in technical yet conversational reporting. Ownership and status ''EE Times'' was launched in 1972 by Gerard G. Leeds of CMP Publications Inc. In 1999, the Leeds family sold CMP to United Business Media for $900 million. After 2000, ''EE Times'' moved more into web publishing. The shift in advertising from print to online began to accelerate in 2007 and the periodical shed staff to adjust to the downturn in revenue. In July 2013, the digital edition migrated to UBM TechWeb's ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
IRE Transactions On Electronic Computers
''IEEE Transactions on Computers'' is a monthly peer-reviewed scientific journal covering all aspects of computer design. It was established in 1952 and is published by the IEEE Computer Society. The editor-in-chief is Ahmed Louri, David and Marilyn Karlgaard Endowed Chair Professor of Electrical and Computer Engineering, George Washington University. According to the ''Journal Citation Reports'', the journal has a 2019 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a scientometric index calculated by Clarivate that reflects the yearly mean number of citations of articles published in the last two years in a given journal, as i ... of 3.131. References External links * Transactions on Computers Computer science journals English-language journals Publications established in 1952 Monthly journals {{comp-sci-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
IRE Transactions On Information Theory
''IEEE Transactions on Information Theory'' is a monthly peer-reviewed scientific journal published by the IEEE Information Theory Society. It covers information theory and the mathematics of communications. It was established in 1953 as ''IRE Transactions on Information Theory''. The editor-in-chief is Muriel Médard (Massachusetts Institute of Technology). As of 2007, the journal allows the posting of preprints on arXiv. According to Jack van Lint, it is the leading research journal in the whole field of coding theory. A 2006 study using the PageRank network analysis algorithm found that, among hundreds of computer science-related journals, ''IEEE Transactions on Information Theory'' had the highest ranking and was thus deemed the most prestigious. '' ACM Computing Surveys'', with the highest impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a scientometric index calculated by Clarivate that reflects the yearly mean number of citati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matematicheskii Sbornik
''Matematicheskii Sbornik'' (russian: Математический сборник, abbreviated ''Mat. Sb.'') is a peer reviewed Russian mathematical journal founded by the Moscow Mathematical Society in 1866. It is the oldest successful Russian mathematical journal. The English translation is ''Sbornik: Mathematics''. It is also sometimes cited under the alternative name ''Izdavaemyi Moskovskim Matematicheskim Obshchestvom'' or its French translation ''Recueil mathématique de la Société mathématique de Moscou'', but the name ''Recueil mathématique'' is also used for an unrelated journal, '' Mathesis''. Yet another name, ''Sovetskii Matematiceskii Sbornik'', was listed in a statement in the journal in 1931 apologizing for the former editorship of Dmitri Egorov, who had been recently discredited for his religious views; however, this name was never actually used by the journal. The first editor of the journal was Nikolai Brashman, who died before its first issue (dedicated to hi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reed–Muller Code
Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in the control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in theoretical computer science. Reed–Muller codes generalize the Reed–Solomon codes and the Walsh–Hadamard code. Reed–Muller codes are linear block codes that are locally testable, locally decodable, and list decodable. These properties make them particularly useful in the design of probabilistically checkable proofs. Traditional Reed–Muller codes are binary codes, which means that messages and codewords are binary strings. When ''r'' and ''m'' are integers with 0 ≤ ''r'' ≤ ''m'', the Reed–Muller code with parameters ''r'' and ''m'' is denoted as RM(''r'', ''m''). When ask ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
David Eugene Muller
David Eugene Muller (November 2, 1924 – April 27, 2008) was an American mathematician and computer scientist. He was a professor of mathematics and computer science at the University of Illinois (1953–92), after which he became an emeritus professor, and was an adjunct professor of mathematics at the New Mexico State University (1995–2008). Muller received his BS in 1947 and his PhD in 1951 in physics from Caltech; an honorary PhD was conferred by the University of Paris in 1989. He was the inventor of the Muller C-element (or Muller C-gate), a device used to implement asynchronous circuitry in electronic computers. He also co-invented the Reed–Muller codes. He discovered the codes, and Irving S. Reed proposed the majority logic decoding for the first time. Furthermore, he invented Muller automata, an automaton model for infinite words. In geometric group theory Muller is known for the Muller–Schupp theorem, joint with Paul Schupp, characterizing finitely gener ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Irving Stoy Reed
Irving Stoy Reed (November 12, 1923 – September 11, 2012) was an American mathematician and engineer. He is best known for co-inventing a class of algebraic error-correcting and error-detecting codes known as Reed–Solomon codes in collaboration with Gustave Solomon. He also co-invented the Reed–Muller code. Reed made many contributions to areas of electrical engineering including radar, signal processing, and image processing. He was part of the team that built the MADDIDA, guidance system for Northrop's Snark cruise missile – one of the first digital computers. He developed and introduced the now-standard Register Transfer Language to the computer community while at the Massachusetts Institute of Technology's Lincoln Laboratory. He was a faculty member of the Electrical Engineering-Systems Department of the University of Southern California from 1962 to 1993. Reed was a member of the National Academy of Engineering (1979) and a Fellow of the IEEE (1973), a winner of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zhegalkin Polynomial
Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (russian: полиномы Жегалкина), also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, ''x''2 = ''x''. Hence a polynomial such as 3''x''2''y''5''z'' is congruent to, and can therefore be rewritten as, ''xyz''. __TOC__ Boolean equivalent Prior to 1927, Boolean algebra had been considered a calculus of logical values with logical operations of conjunction, disjunction, negation, and so on. Zhegalkin showed that all Boolean operations could be written ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Decomposition (computer Science)
Decomposition in computer science, also known as factoring, is breaking a complex problem or system into parts that are easier to conceive, understand, program, and maintain. Overview There are different types of decomposition defined in computer sciences: * In structured programming, ''algorithmic decomposition'' breaks a process down into well-defined steps. * Structured analysis breaks down a software system from the system context level to system functions and data entities as described by Tom DeMarco. * ''Object-oriented decomposition'', on the other hand, breaks a large system down into progressively smaller classes or objects that are responsible for some part of the problem domain. * According to Booch, algorithmic decomposition is a necessary part of object-oriented analysis and design, but object-oriented systems start with and emphasize decomposition into objects.Grady Booch (1994). ''Object-oriented Analysis and Design'' (2nd ed.). Redwood Cita, CA: Benjamin/Cummi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ring Sum Normal Form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or ''Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms: * The entire formula is purely true or false: *: 1 *: 0 * One or more variables are combined into a term by AND (\and), then one or more terms are combined by XOR (\oplus) together into ANF. Negations are not permitted: : a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) * The previous subform with a purely true term: : 1 \oplus a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity (or Parity) Reed–Muller expressions (PPRM). Common uses ANF is a normal form, which means that two equivalent formulas will convert to the same ANF, easily showing whether two formulas are equivalent for automated theorem proving. Unlike other normal form ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
