litex/soc/cores/ecc.py

   1 # This file is Copyright (c) 2018-2019 Florent Kermarrec <florent@enjoy-digital.fr>
   2 # License: BSD
   3
   4 """
   5 Error Correcting Code
   6
   7 Hamming codes with additional parity (SECDED):
   8 - Single Error Correction
   9 - Double Error Detection
  10 """
  11
  12 from functools import reduce
  13 from operator import xor
  14
  15 from migen import *
  16
  17 # Helpers ------------------------------------------------------------------------------------------
  18
  19 def compute_m_n(k):
  20     m = 1
  21     while (2**m < (m + k + 1)):
  22         m = m + 1;
  23     n = m + k
  24     return m, n
  25
  26
  27 def compute_syndrome_positions(m):
  28     r = []
  29     i = 1
  30     while i <= m:
  31         r.append(i)
  32         i = i << 1
  33     return r
  34
  35
  36 def compute_data_positions(m):
  37     r = []
  38     e = compute_syndrome_positions(m)
  39     for i in range(1, m + 1):
  40         if not i in e:
  41             r.append(i)
  42     return r
  43
  44
  45 def compute_cover_positions(m, p):
  46     r = []
  47     i = p
  48     while i <= m:
  49         for j in range(min(p, m - i + 1)):
  50             r.append(i + j)
  51         i += 2*p
  52     return r
  53
  54 # SECDED (Single Error Detection, Double Error Detection) ------------------------------------------
  55
  56 class SECDED:
  57     def place_data(self, data, codeword):
  58         d_pos = compute_data_positions(len(codeword))
  59         for i, d in enumerate(d_pos):
  60             self.comb += codeword[d-1].eq(data[i])
  61
  62     def extract_data(self, codeword, data):
  63         d_pos = compute_data_positions(len(codeword))
  64         for i, d in enumerate(d_pos):
  65             self.comb += data[i].eq(codeword[d-1])
  66
  67     def compute_syndrome(self, codeword, syndrome):
  68         p_pos = compute_syndrome_positions(len(codeword))
  69         for i, p in enumerate(p_pos):
  70             pn = Signal()
  71             c_pos = compute_cover_positions(len(codeword), 2**i)
  72             for c in c_pos:
  73                 new_pn = Signal()
  74                 self.comb += new_pn.eq(pn ^ codeword[c-1])
  75                 pn = new_pn
  76             self.comb += syndrome[i].eq(pn)
  77
  78     def place_syndrome(self, syndrome, codeword):
  79         p_pos = compute_syndrome_positions(len(codeword))
  80         for i, p in enumerate(p_pos):
  81             self.comb += codeword[p-1].eq(syndrome[i])
  82
  83     def compute_parity(self, codeword, parity):
  84         self.comb += parity.eq(reduce(xor,
  85             [codeword[i] for i in range(len(codeword))]))
  86
  87 # ECC Encoder --------------------------------------------------------------------------------------
  88
  89 class ECCEncoder(SECDED, Module):
  90     def __init__(self, k):
  91         m, n = compute_m_n(k)
  92
  93         self.i = i = Signal(k)
  94         self.o = o = Signal(n + 1)
  95
  96         # # #
  97
  98         syndrome = Signal(m)
  99         parity = Signal()
 100         codeword_d = Signal(n)
 101         codeword_d_p = Signal(n)
 102         codeword = Signal(n + 1)
 103
 104         # place data bits in codeword
 105         self.place_data(i, codeword_d)
 106         # compute and place syndrome bits
 107         self.compute_syndrome(codeword_d, syndrome)
 108         self.comb += codeword_d_p.eq(codeword_d)
 109         self.place_syndrome(syndrome, codeword_d_p)
 110         # compute parity
 111         self.compute_parity(codeword_d_p, parity)
 112         # output codeword + parity
 113         self.comb += o.eq(Cat(parity, codeword_d_p))
 114
 115 # ECC Decoder --------------------------------------------------------------------------------------
 116
 117 class ECCDecoder(SECDED, Module):
 118     def __init__(self, k):
 119         m, n = compute_m_n(k)
 120
 121         self.enable = Signal()
 122         self.i = i = Signal(n + 1)
 123         self.o = o = Signal(k)
 124
 125         self.sec = sec = Signal()
 126         self.ded = ded = Signal()
 127
 128         # # #
 129
 130         syndrome = Signal(m)
 131         parity = Signal()
 132         codeword = Signal(n)
 133         codeword_c = Signal(n)
 134
 135         # input codeword + parity
 136         self.compute_parity(i, parity)
 137         self.comb += codeword.eq(i[1:])
 138         # compute_syndrome
 139         self.compute_syndrome(codeword, syndrome)
 140         self.comb += If(~self.enable, syndrome.eq(0))
 141         # locate/correct codeword error bit if any and flip it
 142         cases = {}
 143         cases["default"] = codeword_c.eq(codeword)
 144         for i in range(1, 2**len(syndrome)):
 145             cases[i] = codeword_c.eq(codeword ^ (1<<(i-1)))
 146         self.comb += Case(syndrome, cases)
 147         # extract data / status
 148         self.extract_data(codeword_c, o)
 149         self.comb += [
 150             If(syndrome != 0,
 151                  # double error detected
 152                 If(~parity,
 153                     ded.eq(1)
 154                 # single error corrected
 155                 ).Else(
 156                     sec.eq(1)
 157                 )
 158             )
 159         ]