V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
noname2001
V2EX  ›  程序员

请教大神,要在极不靠谱的信道,通过 320bits 传递 16bits 数据,用什么检错纠错算法比较好,不会丢,只会位翻转

  •  1
     
  •   noname2001 · 2019-09-18 14:51:03 +08:00 · 3433 次点击
    这是一个创建于 1880 天前的主题,其中的信息可能已经有所发展或是发生改变。

    大量冗余,怎么实现可靠传输,谢谢各位了。

    geligaoli
        1
    geligaoli  
       2019-09-18 15:40:09 +08:00
    这么高的冗余,加上校验数据,可以多次重传。
    xemtof
        2
    xemtof  
       2019-09-18 15:40:49 +08:00
    试试海明码。
    geligaoli
        3
    geligaoli  
       2019-09-18 15:43:59 +08:00
    cigarzh
        4
    cigarzh  
       2019-09-18 15:54:20 +08:00
    啥叫极不靠谱? bit flipping 概率很高吗?
    noname2001
        5
    noname2001  
    OP
       2019-09-18 16:12:28 +08:00
    @cigarzh 翻转率极高 一片片的翻转
    noname2001
        6
    noname2001  
    OP
       2019-09-18 16:13:08 +08:00
    @geligaoli rscode 测试过 效果普通 这个页面现在没办法打开 谢谢您回复
    noname2001
        7
    noname2001  
    OP
       2019-09-18 16:15:33 +08:00
    我的场景是通过在画面中增加水印,会通过 h264 和 jpeg 双重有损编码, 增加的信息大范围被损坏,想要一种可靠的算法确定 16bits 信息。目前做的的尝试有 fft 水印、rscode 等
    noname2001
        8
    noname2001  
    OP
       2019-09-18 16:15:56 +08:00
    @geligaoli 是单向传输 多谢
    noname2001
        9
    noname2001  
    OP
       2019-09-18 16:17:02 +08:00
    @xemtof 海明能检测多位翻转吗? 我的应用是正文 2 字节、校验位可以是 28 字节,如果海明能搞定就好了
    lonewolfakela
        10
    lonewolfakela  
       2019-09-18 16:20:27 +08:00
    "翻转率极高 一片片的翻转",“极高”到底是多高呢,有的人可能觉得 10%就很高了,有的人可能到 50%才会说“极高”……另外“一片片”是说反转的位置是连续的么?那么一般在 320bits 里连续的翻转段会有多长呢?
    noname2001
        11
    noname2001  
    OP
       2019-09-18 16:21:42 +08:00
    @lonewolfakela 可能最极端会接近 90%
    noname2001
        12
    noname2001  
    OP
       2019-09-18 16:22:40 +08:00
    所以有效数据位选择 16 位,相当于 6.6%的有效数据
    honeycomb
        13
    honeycomb  
       2019-09-18 16:23:54 +08:00 via Android
    @noname2001 你应当掌握访问 Wiki 的技能,都是写算法的了。
    noname2001
        14
    noname2001  
    OP
       2019-09-18 16:25:04 +08:00
    @lonewolfakela 我增加的水印实际显示和背景相关,所以会出现大片的错误,是全 0 或全 1 这种,连续位翻转的可能性不大 多谢
    noname2001
        15
    noname2001  
    OP
       2019-09-18 16:25:51 +08:00
    @honeycomb 特殊 日寸 其 月, 好失落 多谢
    xemtof
        16
    xemtof  
       2019-09-18 16:33:18 +08:00
    @noname2001 能,有公式 2^k -1 > n+k。
    danielmiao
        17
    danielmiao  
       2019-09-18 17:03:59 +08:00
    @noname2001 从理论上讲高于 50%的错误率是没办法的吧,因为大部分的纠错也好查错也好的基础条件是,正确数据是占多数的,通过多数的正确数据去恢复少数的错误数据,你这 90%的错误率的时候,实际上错误数据要远大于正确数据,而你无法识别那些是正确的那些是错误的,最终的结果是正确数据被错误数据纠正成错误数据了
    noname2001
        18
    noname2001  
    OP
       2019-09-18 17:10:14 +08:00
    需求是给视频照片加不可见水印,通过 264 或 jpeg 编码、解码后还能得到这个信息 多谢
    danielmiao
        19
    danielmiao  
       2019-09-18 17:14:32 +08:00
    根据你的描述,我猜测的场景应该是防止盗录 /截屏,在视频数据里加上了唯一识别码,然后想在提取出来唯一识别码,我感觉换个思路会不会更好,比如在纯中块中间插入某些颜色接近但是能规避 JPEG 合并的像素点之类的方案
    crystom
        20
    crystom  
       2019-09-18 17:23:29 +08:00
    noname2001
        21
    noname2001  
    OP
       2019-09-18 17:24:14 +08:00
    @danielmiao LSB 之类的算法对 JPEG 基本无用 信噪比太低 当成噪声处理掉了
    noname2001
        22
    noname2001  
    OP
       2019-09-18 17:24:37 +08:00
    @crystom 多谢多谢 拜读一下
    noname2001
        23
    noname2001  
    OP
       2019-09-18 17:25:27 +08:00
    @crystom 这个 FFT 这试过了 抗干扰还行 但是运算效率不能满足我的需求 多谢
    danielmiao
        24
    danielmiao  
       2019-09-18 18:11:09 +08:00
    @noname2001 LSB 算法确实信噪比太低;可以考虑类似锐化效果方式,在轮廓边缘加上特定的数据带,从感官上来说无非是图片被锐化过,普通人不仔细看应该不太明显,同时抗编码攻击效果还行,缺点是只能适用于截图,翻拍无效,而且抗变型攻击能力奇差,拉伸缩放以后基本上无效了
    Cooky
        25
    Cooky  
       2019-09-18 18:14:51 +08:00 via Android
    sha256 ?省事
    smdbh
        26
    smdbh  
       2019-09-18 19:23:04 +08:00
    很好奇应用背景
    SeanChense
        27
    SeanChense  
       2019-09-18 19:41:39 +08:00
    应付位翻转难道不应该用格雷码吗?
    bilibilifi
        28
    bilibilifi  
       2019-09-18 19:47:32 +08:00 via iPhone
    信息论有点忘了...记得有库可以干的
    blindie
        29
    blindie  
       2019-09-18 20:07:17 +08:00 via Android
    这不就是典型数字水印的需求吗。直接搜相关论文吧。学校里的时候老师教的是就是 FFT 加水印,现在最新技术是啥就不知道了。又要效果又要速度,那可能得找个权衡。
    favourstreet
        30
    favourstreet  
       2019-09-18 20:10:46 +08:00 via Android
    不开玩笑:把 16Bit 重复 20 遍,20 个 bit 当一个使
    expy
        31
    expy  
       2019-09-18 20:15:15 +08:00
    电影院防盗摄的水印应该有成熟的实现吧。

    搜搜 transcoding resistant digital watermark ?

    https://www.researchgate.net/publication/316486963_Digital_Cinema_Watermarking_State_of_Art_and_Comparison
    ivan_wl
        32
    ivan_wl  
       2019-09-18 20:18:30 +08:00
    BCH, LDPC
    fonlan
        33
    fonlan  
       2019-09-18 22:00:09 +08:00 via Android
    Polar 极化码?
    noname2001
        34
    noname2001  
    OP
       2019-09-19 09:44:08 +08:00
    亲爱的大神们:我们应用的场景是,给视频或图片素材打水印、通过网络播放、在前端通过 hdmi 信号分析画面,判断是否有水印或水印 ID。抓取 hdmi 的设备只能输出 mjpeg 的码流, 所以有 h264 和 jpeg 双重有损编码破坏。bit 全 0 或全 1 损坏率可能达到 90%。
    noname2001
        35
    noname2001  
    OP
       2019-09-19 09:44:47 +08:00
    目前作过的尝试有:
    1 重复法,测试误报率高。
    2 fft 水印:测试速度慢,实时性差,水印人眼勉强辨识,opencv 很难识别,特别影响画面边角纯色区域(条纹很明显)
    3 其他 gayhub/stego-toolkit 这里提到的隐写算法,都无法适应我们应用的场景。
    4 rscode 算法:测试超过 1 半损坏,基本无法还原。
    noname2001
        36
    noname2001  
    OP
       2019-09-19 09:44:58 +08:00
    大家提到的抗转码水印、BCH、LDPC、极化码,我还正在研究,特别是 Polar 感觉好前沿, 哈哈。

    再次感谢大家集思广议,让我受益匪浅。
    noname2001
        37
    noname2001  
    OP
       2019-09-20 14:15:06 +08:00
    别沉 自顶, 想找一个冗余 10 倍,能可靠纠错的算法,这个需求很特别( BT ) 还请大神赐教!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2716 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 08:09 · PVG 16:09 · LAX 00:09 · JFK 03:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.