Error Correcting Codes 2c: Linear Codes - Parity-Check Matrix

แชร์
ฝัง
  • เผยแพร่เมื่อ 22 ต.ค. 2024

ความคิดเห็น • 39

  • @jacobianmigoto
    @jacobianmigoto 4 ปีที่แล้ว +32

    You have saved me so much work trying to decipher my supervisor's notes.

  • @2262sandeep
    @2262sandeep ปีที่แล้ว +6

    This videos playlist should be a mandatory watch for information & coding theory students to really understand the practicalities of the theory

  • @prajwolgyawali6770
    @prajwolgyawali6770 4 ปีที่แล้ว +21

    Parity Check Matrix (H) - 0:30
    Syndrome Vector - 3:00
    Getting d from H - 5:26
    General Hamming Code - 8:00
    Generator Matrix for Parity Matrix- 10:22
    (n, k) code - 11:00
    (n, k, d) code - 11:05

  • @ВиталийОвчаренко-и1н
    @ВиталийОвчаренко-и1н 6 หลายเดือนก่อน +1

    It seems like you've mentioned a topic related to Error Correcting Codes, specifically Linear Codes and Parity-Check Matrices. To help clarify the stages involved in deciding problems related to this topic, I'll break it down into simpler terms.
    1. Understanding Linear Codes: Linear codes are a type of error-correcting codes that are generated by a linear combination of a set of codewords. These codes have a structure that makes them amenable to efficient encoding and decoding techniques.
    2. Parity-Check Matrix: A parity-check matrix is a fundamental tool in the study of linear codes. It is an n x m matrix, where n is the block length of the code, and m is the dimension of the code. The rows of the matrix represent the codewords, and the columns represent the parity-check equations.
    3. Decoding Problems: Decoding is the process of determining the original message from the received message, which may contain errors. In the context of error-correcting codes, the primary goal is to design codes that can efficiently correct errors.
    4. Stages in Deciding Problems: When it comes to deciding problems related to error-correcting codes and parity-check matrices, the process generally involves the following stages:
    a. Problem Formulation: Clearly define the problem you want to solve, such as finding the best way to correct errors in a given code or determining the optimal parity-check matrix for a specific linear code.
    b. Theoretical Analysis: Analyze the problem using mathematical tools and theories related to error-correcting codes and linear algebra. This may involve understanding properties of the code, its distance, and the structure of the parity-check matrix.
    c. Algorithm Development: Develop an algorithm or method to solve the problem. This may involve designing efficient encoding and decoding techniques, such as the well-known decoding algorithms for linear codes, like the Berlekamp-Massey-Sipser algorithm or the Peterson-Gorenstein-Zierler algorithm.
    d. Implementation: Implement the algorithm or method on a computer or in a practical setting. This step may involve designing software, hardware, or protocols that utilize the error-correcting codes and parity-check matrices.
    e. Testing and Evaluation: Test the implemented solution with various inputs and evaluate its performance, such as error correction capability, decoding speed, and memory requirements.
    f. Improvement and Optimization: Based on the results from the testing and

  • @eigenchris
    @eigenchris  4 ปีที่แล้ว +7

    Error at 7:30. H (cT + eT) should NOT be equal to 0 because of the presence of an error.

  • @sebastiankusyk7764
    @sebastiankusyk7764 ปีที่แล้ว +1

    Thanks, I'm constructing some RDS decoder for my radio and now it got more clear for me how error corection works there. There are frames with 16 data and 10 error correction bits, but there's no indication when a frame starts, only from error correction. I made an amplifier with LC filters, signal from radio's tuner chip's DET OUT pin goes through it to ATmega8 which does phase demodulation to get the binary stream and process it.

  • @bentupper4614
    @bentupper4614 4 ปีที่แล้ว +2

    Great videos. Much appreciated. Pacing is good - maybe a little fast for those with rusty LA, but mostly just right with out too much fluff.
    Is there a small error around 7:30? If there's an error in the codeword, shouldn't the output vector no longer be 0-arrow? As in, H (cT + eT) != O?

    • @eigenchris
      @eigenchris  4 ปีที่แล้ว

      Yeah, that's a typo. I'll make a pinned comment about it.

  • @hosampb5593
    @hosampb5593 3 ปีที่แล้ว +2

    you're saving my ass 2 days before my exam

  • @Akira-ho9mf
    @Akira-ho9mf 5 ปีที่แล้ว +1

    good video, very understandable and fast

  • @oceannuclear
    @oceannuclear 3 ปีที่แล้ว

    You write your vertically arranged vectors with ^T?
    I like your funny words, magic man.

  • @malavikaunnikrishnan5769
    @malavikaunnikrishnan5769 3 ปีที่แล้ว

    literally saved my life thank you

    • @martinak1723
      @martinak1723 2 ปีที่แล้ว

      Aayo kahan se ghanshyam

  • @XanderGouws
    @XanderGouws 5 ปีที่แล้ว

    do you think you'd be up to doing one on differential geometry?

  • @shaletpsebastian3019
    @shaletpsebastian3019 3 ปีที่แล้ว

    Great video. Thanks a lot

  • @klevisimeri607
    @klevisimeri607 ปีที่แล้ว

    As always thank you!

  • @thodorisapostolopoulos7519
    @thodorisapostolopoulos7519 4 ปีที่แล้ว

    Hello thanx for the help the explanation was awesome. However what is the logic behind implementing this theory into code in order to generate the matrixes?

    • @eigenchris
      @eigenchris  4 ปีที่แล้ว

      Investigating properties of the matrices helps learn properties about the code itself, such as the rank (number of linearly independent columns), and the minimum distance (column with the smallest number of 1s). It also makes it easy to create the parity-check equations, as seen in later videos.

    • @thodorisapostolopoulos7519
      @thodorisapostolopoulos7519 4 ปีที่แล้ว

      @@eigenchris yeah but if i want to create a generic code for every possible (n,k) aren't there many possible equations and as a result many different matrixes (only the left half of the rows swap but in the end they are different). Is there a specific combination of information bits we XOR?

    • @eigenchris
      @eigenchris  4 ปีที่แล้ว

      @@thodorisapostolopoulos7519 Yes, there are many possible (n,k) codes. Usually you want to pick an (n,k) code that has a minimum distance that suits your error correction needs for the situation you're dealing with. The Hamming (7,4) code is only one possible (7,4) code. There are are others, but they have equal or worse minimum distance. Hamming codes have the property of being "perfect codes" and achieve the best minimum distance d possible for a given n and k.

  • @vietanhang3318
    @vietanhang3318 3 ปีที่แล้ว

    I wonder that how to create matrix H or we use an arbitrary H?

  • @vengerer
    @vengerer 4 ปีที่แล้ว

    Shouldn't you also negate the transpose of H before appending it to an identity matrix to get the generator?

    • @eigenchris
      @eigenchris  4 ปีที่แล้ว +1

      In the integers mod 2, negation doesn't do anything because +1 and -1 do the same thing.

  • @josbinj79
    @josbinj79 4 ปีที่แล้ว

    How do you get the parity matrix ?

  • @minuklee6735
    @minuklee6735 4 ปีที่แล้ว

    thank you very much

  • @philp4684
    @philp4684 3 ปีที่แล้ว

    Is there any particular reason for treating messages & codewords as row vectors when encoding but as column vectors when decoding?
    It seems to me that things would be simpler if messages & codewords were always treated as column vectors. The process of creating a codeword from a message word would then be to pre-multiply (rather than post-multiply) it by a generator matrix. And obviously, this new generator matrix would be the transpose of the generator matrix defined in the video series.
    Also, the process of creating the generator matrix from the parity check matrix as described at 10:33 would instead be to simply insert an identity matrix at the top.
    Then, there'd be no need for any transpositions.

    • @eigenchris
      @eigenchris  3 ปีที่แล้ว

      I'm not sure if there's a good reason. Some textbooks do it the "transposed" way, but most sources I've seen do it the way in this video. I just did it the "popular way" so it would match up with people's textbooks.

  • @alpozen5347
    @alpozen5347 4 ปีที่แล้ว

    saving my exams

  • @gummybears6125
    @gummybears6125 5 ปีที่แล้ว +1

    Your are redefining matrix vector multiplication at 2:19. I would have used a xor function like H cT = xor(v) = [0 0 0]T with v = [1 1 0 1 1 0 0]

    • @ahhuhtal
      @ahhuhtal 4 ปีที่แล้ว

      Not explicitly said in the video, but I think the vector space is taken to have scalar field GF(2). This is then a standard matrix vector product.

  • @AswanthCR7
    @AswanthCR7 5 ปีที่แล้ว

    Love this

  • @saiprasadpappula9135
    @saiprasadpappula9135 3 ปีที่แล้ว +5

    Fast explanation and not clear

  • @leonhardlischka221
    @leonhardlischka221 4 ปีที่แล้ว

    Substraction equals XOR? at 0:50
    How that?
    1100 1100
    - 0011 0011 XOR
    _____ _____
    1001 1111

    • @eigenchris
      @eigenchris  4 ปีที่แล้ว +1

      It's bit-wise subtraction (no carrying digits). Each digit is independent of the others.

    • @ibrahimabarry8939
      @ibrahimabarry8939 3 ปีที่แล้ว

      it's operations in modulo 2 (binary) so 1 + 1 mod 2 = 0 etc

  • @jakeamberson9858
    @jakeamberson9858 2 ปีที่แล้ว

    just wow,,,,,,,tnx

  • @moneerkutt1228
    @moneerkutt1228 4 ปีที่แล้ว

    amazing

  • @DaltonGodfery-l6y
    @DaltonGodfery-l6y 12 วันที่ผ่านมา

    Rempel Roads

  • @martinak1723
    @martinak1723 2 ปีที่แล้ว +1

    Love smoking dope and watch math